Programming Problems Using Heap Memory 135
is in another part of memory that stores the compiled program’s instructions. The
instructions must have addresses because they are stored in memory. Every line of
a program is stored at a memory location. Thus, it is possible to use an address to
specify a particular line of a program. By convention, C uses the name of a function as
the address of the first line of a function. This is the reason a function can be expressed
by a pointer: The function name is the address of the first line of that function.
3. The passed function takes two input arguments. Each argument stores an address.
Again, void * means that the address can be of any type. Section 7.1.7 explains
the meaning of const. This function cannot change the value stored at the address
because const is in front of the type (even though the type is void).
Putting all these factors together, the comparison function must have the following type:
int compare func ( const void * a , const void * b)1
9.2.2 The Comparison Function
What is the comparison function? Why is it necessary to provide a comparison function
as an argument to qsort? The goal of qsort is to sort arrays of any type. This means that
qsort needs to know how to compare two elements in an array without knowing the type.
This is not possible automatically because different types have different sizes. Moreover,
when we talk about programmer-defined structures later in this book, one structure may
contain multiple attributes. It is impossible for qsort to know how to compare programmer-
defined structures. To make it possible, programmers have to tell qsort how to compare
the elements. The comparison function can decide ascending or descending order. The com-
parison function must have the following structure:
// co m parefunc . c1
int compare func ( const void * arg1 , const void * arg2 )2
{3
// convert void * to a known type ( int , char , double ...)4
const type * ptr1 = ( const type *) arg1 ;5
const type * ptr2 = ( const type *) arg2 ;6
// get the value from the address7
const type val1 = * ptr1 ;8
const type val2 = * ptr2 ;9
// compare the value10
i f ( val1 < val2 )11
{ return -1; }12
i f ( val1 == val2 )13
{ return 0; }14
return 1;15
}16
The comparison function has three steps:
1. The arguments arg1 and arg2 point to two distinct elements in the array. If we are
sorting an array of integers, then the array elements are of type int. The pointers
to those elements must be int *. In lines 5 and 6 we convert arg1 and arg2 to the
correct type. This is called type casting. The qsort function knows the size of each
array element because the third argument provides that information.
2. After type casting, ptr1 and ptr2 have the same value (point to the same addresses)
as arg1 and arg2 respectively. The comparison function can now access the data at
those memory locations because the function has changed the pointers to the known
136 Intermediate C Programming
type. It is meaningless comparing addresses. Instead, lines 8 and 9 retrieve the values
stored at those addresses.
3. Lines 11 to 15 return a negative, zero, or positive value based on whether val1 is less
than, equal to, or greater than val2. This comparison function will cause the array
elements to be sorted in ascending order. If we want the elements to be sorted in
the descending order, then we can change lines 11 to 15 so that the function returns
positive, zero, or negative if val1 is less than, equal to, or greater than val2.
The following shows a program that uses qsort to sort an array of integers:
// com pareint .c1
int compare func ( const void * arg1 , const void * arg2 )2
{3
const i n t * ptr1 = ( const i n t *) arg1 ;4
const i n t * ptr2 = ( const i n t *) arg2 ;5
int val1 = * ptr1 ;6
int val2 = * ptr2 ;7
i f ( val1 < val2 ) { return -1; }8
i f ( val1 == val2 ) { return 0; }9
return 1;10
}11
Here is the main function:
/*1
* main q sort . c2
*/3
#in clude < time .h >4
#in clude < stdio .h >5
#in clude < stdlib .h >6
#in clude < string .h >7
#d ef in e RANGE 100008
int compare func ( const void * arg1 , const void * arg2 );9
10
void printArr a y ( i n t * arr , in t size )11
{12
int ind ;13
for ( ind = 0; ind < size ; ind ++)14
{15
printf (" %d ", arr [ ind ]) ;16
}17
printf (" n" );18
}19
20
int main ( i n t argc , char * * argv )21
{22
i f ( argc != 2)23
{24
return EXIT _FAILUR E ;25
}26
int size = strtol ( argv [1] , NULL , 10) ;27
i f ( size <= 0)28
{29
return EXIT _FAILUR E ;30
Programming Problems Using Heap Memory 137
}31
int * arr ;32
arr = malloc ( s i z e o f ( i nt ) * size );33
i f ( arr == NULL )34
{35
return EXIT _FAILUR E ;36
}37
int ind ;38
srand ( time ( NULL )) ; // set the seed39
for ( ind = 0; ind < size ; ind ++)40
{41
arr [ ind ] = rand () % RANGE ;42
}43
printAr r ay ( arr , size );44
qsort (& arr [0] , size , s i z e o f ( i n t ) , compar efunc );45
printAr r ay ( arr , size );46
free ( arr );47
return EXIT _SUCCES S ;48
}49
9.2.3 Execution Examples
The following shows two examples of running the program for two arrays, each with
eight integers:
5045 3603 7935 2430 1019 3445 6339 95451
compar efunc : 5045 36032
compar efunc : 7935 24303
compar efunc : 3603 24304
compar efunc : 3603 79355
compar efunc : 5045 79356
compar efunc : 1019 34457
compar efunc : 6339 95458
compar efunc : 1019 63399
compar efunc : 3445 633910
compar efunc : 2430 101911
compar efunc : 2430 344512
compar efunc : 3603 344513
compar efunc : 3603 633914
compar efunc : 5045 633915
compar efunc : 7935 633916
compar efunc : 7935 954517
1019 2430 3445 3603 5045 6339 7935 954518
7529 6434 2810 3835 7986 8812 127 7131
compar efunc : 7529 64342
compar efunc : 2810 38353
compar efunc : 6434 28104
compar efunc : 6434 38355
compar efunc : 7986 88126
compar efunc : 127 7137
138 Intermediate C Programming
compar efunc : 7986 1278
compar efunc : 7986 7139
compar efunc : 2810 12710
compar efunc : 2810 71311
compar efunc : 2810 798612
compar efunc : 3835 798613
compar efunc : 6434 798614
compar efunc : 7529 798615
127 713 2810 3835 6434 7529 7986 881216
Both runs have eight integers. Before calling qsort, the numbers at line 1 are not
sorted. After calling qsort, the numbers are sorted (in the output above at lines 18 and
16 respectively). These outputs have been generated with the printf function on line 9 of
comparefunc uncommented. By printing one line per comparison made, the outputs tell us
some information about using qsort:
• The comparison function comparefunc is called 16 times in the first example and 14
times in the second example. For the selection sort, the number of comparisons is
always the same for arrays of the same size.
• Some pairs of numbers are not compared. In the first example, 1019 and 7935 are
not compared. In the second example, 127 is not compared with 7529. As mentioned
earlier, qsort uses transitivity to reduce the number of comparisons.
• When comparefunc is called the first time in either example, the first two array
elements (5045 and 3603, 7529 and 6434) are compared. When comparefunc is called
the second time in either example, the next two array elements (7935 and 2403,
2810 and 3835) are compared. However, when comparefunc is called the third time,
different pairs are compared. In the first run, the fourth is the smallest among the
first four elements. In the second run, the third is the smallest among the first four
elements. This is a property of qsort: The relative order of the elements affects which
pairs are compared.
9.2.4 Sorting Strings
The next example uses qsort to sort strings. Consider a program called sortstr printing
the command-line arguments in the ascending order. If we execute this program with the
following arguments:
$ ./sortstr there are several arguments in the command line
the output is
./sortstr
are
arguments
command
in
line
several
the
there
Below is the main function. The function calls qsort using argv as the argument.
1. The first argument of qsort is the address of the first element of the array of strings,
i.e., & argv[0].
Programming Problems Using Heap Memory 139
2. The second argument is the number of strings in the array and it is argc.
3. The third argument is the size of each element. Since each element is a string, the
type is char * and the size is sizeof(char *). Remember that an array of strings is
an array of pointers.
4. The last argument is the comparison function.
// ma inqsort s tr . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < string .h >4
int cmpstrin g p ( const void * arg1 , const void * arg2 );5
int main ( i n t argc , char * * argv )6
{7
int ar ;8
i f ( argc < 2)9
{10
fprintf ( stderr , " Usage : %s < string >... n" , argv [0]) ;11
return EXIT _FAILUR E ;12
}13
qsort (& argv [0] , argc , s i z e o f ( char *) , cm pstringp );14
for ( ar = 0; ar < argc ; ar ++)15
{16
printf (" %s n" , argv [ ar ]) ;17
}18
return EXIT _SUCCES S ;19
}20
The comparison function is similar to the one for an array of integers but the types
are different: arg1 and arg2 are the addresses of strings. Thus, their types are char * *.
Imagine that C has a type called string and arg1 and arg2 store the addresses of strings.
Thus, arg1 and arg2 are of type string *. Since string is actually char * in C, arg1 and
arg2 are of type char * *. After casting the types of arg1 and arg2, the program then
needs to get the strings from the addresses by adding * to retrieve the values stored at the
addresses. Finally, the program uses strcmp to compare the two strings.
// com parestr .c1
#in clude < string .h >2
int cmpstrin g p ( const void * arg1 , const void * arg2 )3
{4
// ptr1 and ptr2 are string *5
// string is char * , thus ptr1 and ptr2 are char * *6
const char * const * ptr1 = ( const char * *) arg1 ;7
const char * const * ptr2 = ( const char * *) arg2 ;8
const char * str1 = * ptr1 ; // type : string9
const char * str2 = * ptr2 ;10
return strcmp ( str1 , str2 );11
}12
Quick sort is faster than selection sort because quick sort uses transitivity. How much
faster is it? Fig. 9.1 compares the execution times for sorting arrays of different sizes. When
the number of elements increases, the execution time increases for both quick sort and
selection sort. However, the execution time for selection sort increases much faster, i.e., the
ratio increases. The ratio actually increases to infinity as the size of the array increases. This
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.