238 Intermediate C Programming
15.4.4 Example 4
In the fourth example we consider the sequence <2, 3, 1>. The first number, 2, is read
and pushed on to the stack.
2
The second number, 3, is read. Since 2 is smaller than 3, 2 is popped from the stack and 3
is pushed on to the stack.
3
The third number, 1, is read. Since 1 is smaller than 3, 1 is pushed on to the stack.
1
3
The numbers are popped and the result is <2, 1, 3>.
There is a problem: The popped sequence is not sorted. Stack sort can sort some se-
quences of numbers but fails to sort the others. Is there a way to determine whether a
sequence of numbers is “stack sortable”?
15.4.5 Stack Sortable
Let M be the largest value of the whole sequence. Without loss of generality, a sequence
of numbers can be divided into three parts: A before M, M , and B after M . It is possible
that the first or third parts (or both) are empty. If M is the first number in the sequence,
then A is empty. If M is the last number in the sequence, then B is empty.
A: before M M B: after M
Step 5 of the algorithm pops all the numbers in the stack when M is read. Suppose M
A
is the largest value in A. All the values must obey M
A
< M , because M is the largest value.
Suppose m
B
is the smallest value in B. When M is pushed to the stack, every number in A
must have already been popped. If m
B
< M
A
, m
B
should be popped before M
A
is popped.
However, when M is pushed, M
A
has already been popped and there is no chance for m
B
to be popped before M
A
is popped. As a result, stack sort fails for this sequence. In the last
example, <2, 3, 1>, M is 3, M
A
is 2, and m
B
is 1. The condition m
B
< M
A
is satisfied so
<2, 3, 1> is not stack sortable.
Is this sequence <1, 5, 2, 3, 5, 4> stack sortable? Note that the largest value 5 appears
twice in this sequence. Following the procedure described earlier, the first number is pushed
to the stack.
1
The next number 5 is larger than 1 so 1 is popped and 5 is pushed.
5
The third number 2 is smaller than 5 and it is pushed.
Programming Problems Using Recursion 239
2
5
The next number is 3 so 2 is popped from the stack and 3 is pushed.
3
5
The next number is 5 so 3 is popped and 5 is pushed.
5
5
The last number 4 is pushed.
4
5
5
Finally, all numbers are popped and the output sequence is 1, 2, 3, 4, 5, 5. It is sorted.
Thus, <1, 5, 2, 3, 5, 4> is stack sortable.
If the same largest value M (5 in this example) appears multiple times, which M should
be chosen for breaking the sequence into A, M , and B? Should it be the first M , the second
M, the last one, or will any one do? The answer is the first M because we compare only the
smallest element in B and do not care about the largest element in B. If we choose an M
other than the first, then the first M is in A and the sequence would never be considered
stack sortable, which is a mistake.
After breaking the sequence into the three parts, the same procedure is applied recur-
sively to A and B to determine whether in turn they are stack sortable. The algorithm for
checking stack sortable is described as follows:
1. An empty sequence is stack sortable. This is a base case.
2. Find the largest value in the sequence. If this value appears multiple times in the
array, select the first one.
3. Divide the sequence into three parts.
4. If both A and B are empty, then the sequence is stack sortable. The sequence has
only one element. This is another base case.
5. If A is empty (B must not be empty), then jump to step 9.
6. If B is empty (A must not be empty), then jump to step 8.
7. Since neither A nor B is empty, find M
A
and m
B
. If M
A
> m
B
, then the sequence is
not stack sortable. This is another base case.
8. Recursively check whether A is stack sortable.
9. Recursively check whether B is stack sortable.
The following implementation checks whether a sequence is stack sortable. We have used
the permutation program to generate all possible test cases.
// stac ksort . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < string .h >4
int findIndex ( i n t * arr , i nt first , in t last , int maxmin )5
// find the index of the largest or s m allest element6
// the range is expressed by the i n d exe s [ first , last ]7
// maxmin = 1: find largest , maxmin = 0: find smallest8
240 Intermediate C Programming
{9
int ind ;10
int answer = first ;11
for ( ind = first + 1; ind <= last ; ind ++)12
{13
i f ((( maxmin == 1) && ( arr [ answer ] < arr [ ind ]) ) ||14
(( maxmin == 0) && ( arr [ answer ] > arr [ ind ])) )15
{16
answer = ind ;17
}18
}19
return answer ;20
}21
int findMa xIndex ( i n t * arr , in t first , i nt last )22
{23
return findInde x ( arr , first , last , 1) ;24
}25
int findMi nIndex ( i n t * arr , in t first , i nt last )26
{27
return findInde x ( arr , first , last , 0) ;28
}29
int isSt a ckSor table ( i n t * arr , in t first , i n t last )30
// check whether the range of the array is so r t able31
// return 1 if the range of the array is so r table32
// return 0 if the range of the array is not s ortable33
{34
i f ( first >= last ) // no or one e l e men t is stack so r t able35
{36
return 1;37
}38
int maxIndex = findM axIndex ( arr , first , last );39
// conside r the four cases40
// both A and B are empty41
// The array has only one element , it is stack sortable42
// already checked earlier43
44
// A is empty , B is not empty45
// check whether B is stack sortable46
i f ( first == ma x Index )47
{48
return isS tackSo rtabl e ( arr , first + 1, last );49
}50
// A is not empty , B is empty51
// check whether A is stack sortable52
i f ( maxInde x == last )53
{54
return isS tackSo rtabl e ( arr , first , last - 1) ;55
}56
// neither is empty57
int maxAIndex = fin dMaxInd ex ( arr , first , maxI n dex - 1) ;58
int minBIndex = fin dMinInd ex ( arr , m a xIndex + 1, last );59
Programming Problems Using Recursion 241
i f ( arr [ maxAIndex ] > arr [ minBInd e x ])60
{61
return 0; // not stack so r t able62
}63
int sortA = isSt ackSor table ( arr , first , maxInd e x - 1) ;64
int sortB = isSt ackSor table ( arr , max I n dex + 1, last );65
return ( sortA && sortB ); // return 1 only if both are 166
}67
void printArr a y ( i n t * arr , in t length )68
{69
i f ( i sStack Sortab le ( arr , 0 , length - 1) == 0)70
{71
return ;72
}73
int ind ;74
for ( ind = 0; ind < length - 1; ind ++)75
{76
printf (" %d" , arr [ ind ]) ;77
}78
printf (" %d n" , arr [ length - 1]) ;79
}80
void swap ( i n t * a , i nt * b )81
{82
int s = * a;83
* a = * b ;84
* b = s ;85
}86
void permute Help ( in t * arr , in t ind , i n t num )87
{88
i f ( ind == num )89
{90
printAr r ay ( arr , ind ) ;91
return ;92
}93
int loc ; // d e stinatio n of arr [ ind ]94
for ( loc = ind ; loc < num ; loc ++)95
{96
swap (& arr [ ind ], & arr [ loc ]) ;97
permut eHelp ( arr , ind + 1 , num );98
swap (& arr [ ind ], & arr [ loc ]) ; // swap back99
}100
}101
void permute ( in t * arr , i n t num )102
{103
permut eHelp ( arr , 0, num );104
}105
int main ( i n t argc , char * argv [])106
{107
i f ( argc != 2)108
{109
return EXIT _FAILUR E ;110
242 Intermediate C Programming
}111
int num = ( in t ) strtol ( argv [1] , NULL , 10) ;112
i f ( num <= 0)113
{114
return EXIT _FAILUR E ;115
}116
int * arr ;117
arr = malloc ( s i z e o f ( i nt ) * num ) ;118
int ind ;119
for ( ind = 0; ind < num ; ind ++)120
{121
arr [ ind ] = ind + 1;122
}123
permute ( arr , num ) ;124
free ( arr );125
return EXIT _SUCCES S ;126
}127
For an array of n distinct numbers, there are n! permutations. Among them,
1
n+1
C
2n
n
are stack sortable. This is called the Catalan number. The proof will be given later in this
book.
15.5 Tracing a Recursive Function
This problem asks you to understand a program with a recursive function. Please solve
the problem without running the program in a computer. What is the output of this pro-
gram?
// trace1 . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
int func ( i n t n , in t * count )4
{5
(* count ) ++;6
i f (( n == 0) || ( n == 1) )7
{8
return 1;9
}10
int val = 0;11
int a = func (n - 1, count ) ;12
int b = func (n / 2, count ) ;13
val += a + b ;14
return val ;15
}16
int main ( i n t argc , char * * argv )17
{18
int count = 0;19
int val = 4;20
int fv = func (val , & count ) ;21
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.