228 Intermediate C Programming
Continuing the algorithm, the value of low increases because 16 is smaller than 19.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 16 8 31 6 42 28 23 51 33
variable pivot low high
Because 8 is smaller than 19, low increments again.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 16 8 31 6 42 28 23 51 33
variable pivot low high
Because 31 is greater than 19, low stops here. Since 23 is greater than the pivot, high
decrements.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 16 8 31 6 42 28 23 51 33
variable pivot low high
The index high decrements twice more, and the value at high is 6.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 16 8 31 6 42 28 23 51 33
variable pivot low high
Now the values at low and high are swapped.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 19 7 12 16 8 6 31 42 28 23 51 33
variable pivot low high
If low increments, it will meet high. This means that the array has been divided into
three parts: (i) the first element, which is the pivot, (ii) the part that is smaller than the
pivot, and (iii) the part that is greater than the pivot.
Now the value at low and the pivot are swapped.
index 0 1 2 3 4 5 6 7 8 9 10 11
value 6 7 12 16 8 19 31 42 28 23 51 33
variable low high
The algorithm next sorts part (ii) using the same procedure.
index 0 1 2 3 4
value 6 7 12 16 8
variable pivot low high
The algorithm also sorts part (iii) using the same procedure.
index 6 7 8 9 10 11
value 31 42 28 23 51 33
variable pivot low high
A sample implementation of quick sort is shown below. The function quickSort takes
only two arguments: the array and its length. The recursive function needs three argu-
ments: the array and the range of indexes to be sorted. Thus, a helper function called
quickSortHelp is created. This helper function divides the array elements in the specified
range into three parts and recursively sorts the first and the third parts.
Programming Problems Using Recursion 229
// quic ksort . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < time .h >4
#in clude < string .h >5
#d ef in e RANGE 100006
int * arrGen ( i n t size ) ;7
// generat e a sorted array of integers8
void swap ( i n t * a , i nt * b );9
s t a t i c void quickS o rtHelp ( in t * arr , i n t first , i nt last )10
{11
// [ first , last ]: range of valid in d e x e s ( not last - 1)12
i f ( first >= last ) // no need to sort one or no element13
{14
return ;15
}16
#i f d e f DEBUG17
printf (" first = %d , last = %d n" , first , last );18
#e ndif19
int pivot = arr [ first ];20
int low = first + 1;21
int high = last ;22
while ( low < high )23
{24
while (( low < last ) && ( arr [ low ] <= pivot ) )25
{26
// <= so that low will incre ment when arr [ low ]27
// is the same as pivot , using < will stop28
// in crement i ng low when arr [ low ] is the same29
// as pivot and the outer while loop will not stop30
low ++;31
}32
while (( first < high ) && ( arr [ high ] > pivot ) )33
{34
high --;35
}36
i f ( low < high )37
{38
swap (& arr [ low ], & arr [ high ]) ;39
}40
}41
i f ( pivot > arr [ high ])42
{43
swap (& arr [ first ], & arr [ high ]) ;44
}45
quick SortHel p ( arr , first , high - 1) ;46
quick SortHel p ( arr , low , last );47
}48
void quickSort ( i n t * arr , i nt len )49
{50
quick SortHel p ( arr , 0, len - 1) ;51
230 Intermediate C Programming
}52
void printArr a y ( i n t * arr , in t len ) ;53
int main ( i n t argc , char * * argv )54
{55
i f ( argc < 2)56
{57
printf (" need a positive integer n ") ;58
return EXIT _FAILUR E ;59
}60
i f ( argc == 3)61
{62
srand ( strtol ( argv [2] , NULL , 10) );63
}64
e l s e65
{66
srand ( time ( NULL )) ; // set the seed67
}68
int num = strtol ( argv [1] , NULL , 10) ;69
i f ( num <= 0)70
{71
printf (" need a positive integer n ") ;72
return EXIT _FAILUR E ;73
}74
int * arr = arrGen ( num ) ;75
printAr r ay ( arr , num ) ;76
quickSort ( arr , num ) ;77
printAr r ay ( arr , num ) ;78
free ( arr );79
return EXIT _SUCCES S ;80
}81
void swap ( i n t * a , i nt * b )82
{83
int s = * a;84
* a = * b ;85
* b = s ;86
}87
int * arrGen ( i n t size )88
{89
i f ( size <= 0)90
{91
return NULL ;92
}93
int * arr = malloc ( s i z e o f ( i n t ) * size );94
i f ( arr == NULL )95
{96
return NULL ;97
}98
int ind ;99
for ( ind = 0; ind < size ; ind ++)100
{101
arr [ ind ] = rand () % RANGE ;102
Programming Problems Using Recursion 231
}103
return arr ;104
}105
void printArr a y ( i n t * arr , in t len )106
{107
int ind ;108
int sorted = 1;109
for ( ind = 0; ind < len ; ind ++)110
{111
#i f d e f DEBUG112
printf (" %d ", arr [ ind ]) ;113
#e ndif114
i f (( ind > 0) && ( arr [ ind ] < arr [ ind -1]) )115
{116
sorted = 0;117
}118
}119
printf (" nsorted = % dn n " , sorted ) ;120
}121
This implementation introduces a new way to debug. Lines 17 and 19 use #ifdef DEBUG
and #endif to enclose debugging code. If this program is compiled the normal way, the lines
between #ifdef DEBUG and #endif are skipped by the compiler. In other words, the line
(or lines) between #ifdef DEBUG and #endif has (or have) no effect. This is useful if the
program prints too many debugging messages. If you want to see the debugging messages,
compile the program in the following way:
$ gcc -g -Wall -Wshadow -DDEBUG quicksort.c -o quicksort
When adding -DDEBUG (it is -D followed by the symbol after #ifdef) after gcc, the
debugging messages are shown. This flag tells gcc to define the symbol DEBUG. You can
define other symbols by adding -D in front of the symbol after the gcc command. It is also
possible to add -DDEBUG to CFLAGS in Makefile.
You may have noticed that the function printArray also checks whether the array is
sorted. This is another debugging technique. Visually inspecting whether an array is sorted
is useful for an array with only a few elements. Instead of using visual inspection, the
program automatically determines whether or not the array is sorted. Making the program
check for its own correctness allows us to test quickSort and its helper function with an
array of thousands of elements.
Another debugging technique is to use argv[2] to set the seed of the random numbers.
To test the program, you probably want to use random numbers so that the tests can cover
different scenarios. However, we need some way to repeat the test if a problem is found, and
that means we must be able to control the sequence of random numbers. One solution is to
use a command-line argument. If this argument is present, the random number generator
is seeded correspondingly, and then the same sequence of numbers is generated. Without
giving this command-line argument, the seed is determined by the system clock, and the
sequence will almost certainly be different every time the program is run.
At first glance, this program may appear straightforward. A closer look, however, re-
veals that some common mistakes can easily occur. The helper function’s second and third
arguments specify the range of indexes that is being sorted. This function assumes last is
a valid index and quickSort thus must use len - 1. If line 51 uses len, then the program
may access an invalid memory location because len is not a valid index. As explained in
232 Intermediate C Programming
Section 7.2.2, sometimes accessing an invalid memory address does not seem to cause prob-
lems but the program is still wrong. If the program is compiled on different platforms, with
different compilers, or if it is run enough times, then at some stage it will fail. Running
valgrind is extraordinarily helpful in picking up these types of errors. If line 51 uses len,
then valgrind reports:
==8895== Invalid read of size 4
==8895== at 0x4007A0: quickSortHelp (quicksort.c:36)
The problem occurs when high is last. Please note that last can be len.
Now look at line 25, which uses arr[low] <= pivot. What happens if it is rewritten
as arr[low] < pivot? This small difference can cause problems when some of the array’s
elements have the same value as the pivot. When this occurs and line 25 has no =, then low
does not increment. If arr[high] is smaller than the pivot, then high does not decrement.
As a result, neither low nor high change and the program enters an infinite loop because
low < high is always true.
Some implementations of quick sort select random (not the first) array elements for the
pivots. Why? Quick sort can be fast due to transitivity. If the original array is already
sorted then quick sort is not faster because the first part (the part smaller than the pivot)
is empty, and the program does not take advantage of transitivity. Using a random element
in the array for the pivot reduces the chance when the pivot is always the smallest element
in the sorted array.
15.3 Permutations and Combinations
Permutations can be generated using recursion based on the following idea: Swap the
first item with any of the later locations, and then swap the second item with any of the
later locations, and so on. The following example should make this clearer:
A B C D
The first item, A, may appear in the first, second, third, or fourth column.
A
A
A
A
Every time A moves, it is swapped with the item originally at that column. The second
item, B, may also appear in the first, second, third, or fourth column. However, we need to
exclude putting B in the first column because A appears in the second column by swapping
A and B. Thus, B already has a chance to be moved to the first column and needs to be
moved to only the second (original location), third, and fourth columns.
B
B
B
Similarly, C may appear in the third or the fourth column.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.