130 Intermediate C Programming
parts: the part before ind1 has been sorted and the part after ind1 has not been sorted. To
sort the second part, we select the smallest inside this part and move it to the beginning of
the second part. Then, ind1 increases, effectively shrinking the second part.
Line 20 initializes minind to ind1. This stores the index of the smallest element seen
so far in the second part of the array. Then, lines 21 to 27 find the index of the smallest
element in the second part of the array. Lines 28 to 32 move the smallest value to the correct
place in the array. This is achieved by swapping the smallest value from its current location
to the correct location. The number of comparisons (line 23) depends on the number of
elements and is independent of the actual values of the elements.
This program uses the same swap function described in Section 4.4. The swap function
is marked static. A static function can be called by functions in the same file only. A static
function is invisible outside this file.
Consider the following example: The input values are 1694, 8137, 609, 7118, 5614, and
8848. The smallest value is the third element (index is 2). The first iteration of ind1 swaps
the first (index is 0) and the third elements and now the array’s elements are 609, 8137,
1694, 7118, 5614, and 8848. The following table shows the array’s elements in each iteration,
just before calling swap:
ind1 minind Sorted Unsorted
0 2 1694 8137 609 7118 5614 8848
1 2 609 8137 1694 7118 5614 8848
2 4 609 1694 8137 7118 5614 8848
3 3 609 1694 5614 7118 8137 8848
4 4 609 1694 5614 7118 8137 8848
5 5 609 1694 5614 7118 8137 8848
This is the sorted array: 609 1694 5614 7118 8137 8848. The main function has a few
places that require explanation:
• This main function stores the data in an array. The size of the array is given by
argv[1].
• Before using argv[1], the program must check that argc is 2. If argc is 1, then
argv[1] does not exist (argv[0] does) and attempting to access argv[1] will crash
the program.
• The program uses strtol to convert argv[1] from a string to an integer.
• The main function must call malloc to allocate heap memory for the array before
reading data from the file.
• The main function must call free to release the heap memory of the array before the
program ends.
/*1
* main . c2
*/3
#in clude < stdio .h >4
#in clude < stdlib .h >5
#in clude < string .h >6
#in clude " mysort .h "7
int main ( i n t argc , char * * argv )8
{9
i f ( argc != 2)10
{11
return EXIT _FAILUR E ;12
}13
int number = strtol ( argv [1] , NULL , 10) ;14
Programming Problems Using Heap Memory 131
int * arr ;15
arr = malloc ( s i z e o f ( i nt ) * number ) ;16
i f ( arr == NULL )17
{18
return EXIT _FAILUR E ;19
}20
int ind ;21
for ( ind = 0; ind < number ; ind ++)22
{23
scanf (" %d" , & arr [ ind ]) ;24
}25
mysort ( arr , number );26
for ( ind = 0; ind < number ; ind ++)27
{28
printf (" %d n" , arr [ ind ]) ;29
}30
free ( arr );31
return EXIT _SUCCES S ;32
}33
The Makefile has a section for testing. It runs the program for the four test cases and
compares the outputs with the expected results.
GCC = gcc1
CFLAGS = -g - Wall - Wshadow2
OBJS = mysort .o main .o3
HDRS = mysort .h4
5
mysort : $( OBJS ) $ ( HDRS )6
$( GCC ) $ ( CFLAGS ) $( OBJS ) -o $@7
8
.c .o:9
$( GCC ) $ ( CFLAGS ) -c $ *. c10
11
test : mysort12
./ mysort 6 < input6 > output613
diff o u t pu t 6 exp e cted614
./ mysort 20 < input20 > output2015
diff o utput20 expecte d2016
./ mysort 50 < input50 > output5017
diff o utput50 expecte d5018
./ mysort 100 < input100 > output10 019
diff output100 expected1 0020
21
testgen : t e st gen . c22
$( GCC ) testgen . c -o testgen23
24
inputgen : testgen25
./ testgen 6 > input626
./ testgen 20 > input2027
./ testgen 50 > input5028
./ testgen 100 > input10029
132 Intermediate C Programming
sort -n input6 > expecte d 630
sort -n input20 > e xpected2031
sort -n input50 > e xpected5032
sort -n input100 > ex p ected10033
34
clean :35
/ bin / rm -f temp * testgen input *36
/ bin / rm -f expected * *. o output * mysort37
As we can see, Makefile can substantially simplify testing, because it saves a lot of time
typing these commands over and over again.
9.1.4 Using valgrind to Detect Memory Leaks
Many people stop when their programs produce correct outputs; however this is prob-
lematic. Producing correct outputs is only one part of software development. We also need
to check hidden errors. Section 5.4 explained how to use valgrind to check invalid mem-
ory accesses that may result in security flaws and unpredictable behavior. We can also use
valgrind to detect memory leaks. This is the new Makefile checking memory leaks:
GCC = gcc1
CFLAGS = -g - Wall - Wshadow2
VALGRIND = valgrind -- tool = memc h eck --leak - check = full3
VALGRIND += -- verbose -- log - file =4
OBJS = mysort .o main .o5
HDRS = mysort .h6
7
mysort : $( OBJS ) $ ( HDRS )8
$( GCC ) $ ( CFLAGS ) $( OBJS ) -o $@9
10
.c .o:11
$( GCC ) $ ( CFLAGS ) -c $ *. c12
13
test : mysort14
$( VALGRIND ) log6 ./ mysort 6 < input6 > output615
diff o u t pu t 6 exp e cted616
$( VALGRIND ) log20 ./ mysort 20 < input20 > o utput2017
diff o utput20 expecte d2018
$( VALGRIND ) log50 ./ mysort 50 < input50 > o utput5019
diff o utput50 expecte d5020
$( VALGRIND ) log100 ./ mysort 100 < i n put100 > out p ut10021
diff output100 expected1 0022
23
testgen : t e st gen . c24
$( GCC ) testgen . c -o testgen25
26
inputgen : testgen27
./ testgen 6 > input628
./ testgen 20 > input2029
./ testgen 50 > input5030
./ testgen 100 > input10031
sort -n input6 > expecte d 632
Programming Problems Using Heap Memory 133
sort -n input20 > e xpected2033
sort -n input50 > e xpected5034
sort -n input100 > ex p ected10035
36
clean :37
/ bin / rm -f temp * testgen input * expected *38
/ bin / rm -f *. o output * mysort log *39
If we remove
free ( arr );31
near the end of main, then the program will leak memory. The log files generated by
valgrind will show something like:
ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)
at the bottom. If we look backwards in the log file, we will something similar to:
==4645== 24 bytes in 1 blocks are definitely lost in loss record 1 of 1
==4645== by 0x40070F: main (main.c:16)
==4645==
==4645== LEAK SUMMARY:
==4645== definitely lost: 24 bytes in 1 blocks
The program leaks 24 bytes of memory, and the memory was allocated at line 16 in
main.c. Why does the program leak 24 bytes? The program allocates space for 6 inte-
gers by calling malloc. Each integer occupies 4 bytes so the program leaks 24 bytes. (i.e.,
sizeof(int) × 4 = 24.) If we put the free statement back, valgrind reports
All heap blocks were freed -- no leaks are possible
We should always check valgrind’s reports when writing programs. Remember that if
valgrind reports problems then the program has problems. If valgrind reports no prob-
lems, then the program may still have problems but valgrind failed to detect them.
9.2 Sort Using qsort
The previous problem asks you to write a program that sorted an array of integers.
The program uses selection sort. Even though the algorithm is easy to understand and to
implement, it is inefficient when used with large arrays. The inefficiency occurs because
the algorithm does not use the transitivity of integers. What is transitivity? Consider three
integers x, y, and z. If x > y and y > z, then x > z. C provides a function called qsort and
it uses the quick sort algorithm. It is a much faster general-purpose sorting algorithm than
selection sort because it uses transitivity to dramatically reduce the number of comparisons
between elements.
9.2.1 qsort
First, let’s examine the manual for qsort:
134 Intermediate C Programming
NAME
qsort - sorts an array
SYNOPSIS
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t Size,
int(*compar)(const void *, const void *));
DESCRIPTION
The qsort() function sorts an array with nmemb elements of size
Size. The base argument points to the start of the array.
The contents of the array are sorted in ascending order
according to a comparison function pointed to by compar, which is
called with two arguments that point to the objects being compared.
The comparison function must return an integer less than, equal
to, or greater than zero if the first argument is considered to be
respectively less than, equal to, or greater than the second. If two
members compare as equal, their order in the sorted array is
undefined.
RETURN VALUE
The qsort() function returns no value.
It is important to become comfortable with the manual pages for C functions. They may
appear terse at first, but they are well written. Their target audience is the people who have
some familiarity with C. The manual says qsort requires four arguments:
1. base: the address of the first element of the array. This should be & arr[0].
2. the number of elements (members) in the array.
3. the size of each element in bytes. If it is an integer array, this argument should be
sizeof(int). Some students write 4 and this is wrong. The size of an integer is not
necessarily 4. Your program will fail if the size is not 4.
4. a comparison function.
What is void *? Why is void * the type of base? It means that the memory address
can point to any type. This is important for a general-purpose function. Thus we can use
qsort to sort any type of array. It can be int *, or char *, or double *, as long as it is
an address of a valid array. The type being pointed to is specified indirectly by the third
argument. The third argument informs qsort of the size of each array element. Among the
four arguments, the last one requires a new concept: passing a function as an argument to
another function.
1. int(*compar)(const void *, const void *) means that this argument is the
name of a function. How do I know it is a function? Because of the parenthesis after
(*compar).
2. int before (* compar) means that the passed function must return an integer. Why
is there an asterisk? Because the name of a function is a pointer to the function.
Section 2.3 said that whenever a function is called, the return location is pushed onto
the call stack. What does this mean? Each line of a program has a location (i.e.,
an address). This address is neither in the call stack, nor in the heap. The address
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset