C Programming For Beginners (2015)

To give an example of how a search may be used, consider the voting problem of the last chapter. After the votes have been tallied, our arrays name and vote look like this (remember we did not use name[0] and vote[0]):

	name	vote
1	Victor Taylor	4
2	Denise Duncan	3
3	Kamal Ramdhan	6
4	Michael Ali	4
5	Anisa Sawh	6
6	Carol Khan	2
7	Gary Olliverie	3

Suppose we want to know how many votes Carol Khan received. We would have to search for her name in the name array. When we find it (in position 6), we can retrieve her votes from vote[6]. In general, if a name is in position n, the number of votes received will be vote[n].

We modify our search function to look for a name in the name array:

//search for key from name[lo] to name[hi]

int search(char name[][MaxNameLength+1], char key[], int lo, int hi) {

for (int h = lo; h <= hi; h++)

if (strcmp(key, name[h]) == 0) return h;

return -1;

}

Recall that we compare two strings using strcmp. And in order to use any pre-defined string function, we must use the directive

#include <string.h>

at the head of our program.

We can use this function as follows:

n = search(name, "Carol Khan", 1, 7);

if (n > 0) printf("%s received %d vote(s)\n", name[n], vote[n]);

else printf("Name not found\n");

Using our sample data, search will return 6 which will be stored in n. Since 6 > 0, the code will print

Carol Khan received 2 vote(s)

9.2 Selection Sort

Consider the voting program of Section 8.14. In Program P8.8, we printed the results in the order in which the names were given. But suppose we want to print the results in alphabetical order by name or in order by votes received, with the winner(s) first. We would have to rearrange the names or the votes in the order we want. We say we would have to sort the names in ascending order or sort the votes in descending order.

Sorting is the process by which a set of values are arranged in ascending or descending order. There are many reasons to sort. Sometimes we sort in order to produce more readable output (for example, to produce an alphabetical listing). A teacher may need to sort her students in order by name or by average score. If we have a large set of values and we want to identify duplicates, we can do so by sorting; the repeated values will come together in the sorted list. There are many ways to sort. We will discuss a method known as selection sort.

Consider the following array:

num
57	48	79	65	15	33	52
0	1	2	3	4	5	6

Sorting num in ascending order using selection sort proceeds as follows:

1^st pass

§ Find the smallest number in positions 0 to 6; the smallest is 15, found in position 4.

§ Interchange the numbers in positions 0 and 4. We get this:

§

num
15	48	79	65	57	33	52
0	1	2	3	4	5	6

2^nd pass

§ Find the smallest number in positions 1 to 6; the smallest is 33, found in position 5.

§ Interchange the numbers in positions 1 and 5. We get this:

§

num
15	33	79	65	57	48	52
0	1	2	3	4	5	6

3^rd pass

§ Find the smallest number in positions 2 to 6; the smallest is 48, found in position 5.

§ Interchange the numbers in positions 2 and 5. We get this:

§

num
15	33	48	65	57	79	52
0	1	2	3	4	5	6

4^th pass

§ Find the smallest number in positions 3 to 6; the smallest is 52, found in position 6.

§ Interchange the numbers in positions 3 and 6. We get this:

§

num
15	33	48	52	57	79	65
0	1	2	3	4	5	6

5^th pass

§ Find the smallest number in positions 4 to 6; the smallest is 57, found in position 4.

§ Interchange the numbers in positions 4 and 4. We get this:

§

num
15	33	48	52	57	79	65
0	1	2	3	4	5	6

6^th pass

§ Find the smallest number in positions 5 to 6; the smallest is 65, found in position 6.

§ Interchange the numbers in positions 5 and 6. We get this:

§

num
15	33	48	52	57	65	79
0	1	2	3	4	5	6

and the array is now completely sorted.

If we let h go from 0 to 5, on each pass:

§ We find the smallest number from positions h to 6.

§ If the smallest number is in position s, we interchange the numbers in positions h and s.

§ For an array of size n, we make n-1 passes. In our example, we sorted 7 numbers in 6 passes.

The following is an outline of the algorithm:

for h = 0 to n - 2

s = position of smallest number from num[h] to num[n-1]

swap num[h] and num[s]

endfor

In Section 8.13, we wrote a function to return the position of the smallest number in an integer array. Here it is for easy reference:

//find position of smallest from num[lo] to num[hi]

int getSmallest(int num[], int lo, int hi) {

int small = lo;

for (int h = lo + 1; h <= hi; h++)

if (num[h] < num[small]) small = h;

return small;

} //end getSmallest

We also wrote a function swap which swapped two elements in a a character array. We now re-write swap to swap two elements in an integer array:

//swap elements num[i] and num[j]

void swap(int num[], int i, int j) {

int hold = num[i];

num[i] = num[j];

num[j] = hold;

} //end swap

With getSmallest and swap, we can code the algorithm, above, as a function selectionSort. To emphasize that we can use any names for our parameters, we write the function to sort an integer array called list. To make it general, we also tell the function which portion of the array to sort by specifying subscripts lo and hi. Instead of the loop going from 0 to n-2 as in the algorithm, it now goes from lo to hi-1, just a minor change for greater flexibility.

//sort list[lo] to list[hi] in ascending order

void selectionSort(int list[], int lo, int hi) {

int getSmallest(int [], int, int);

void swap(int [], int, int);

for (int h = lo; h < hi; h++) {

int s = getSmallest(list, h, hi);

swap(list, h, s);

}

} //end selectionSort

We now write Program P9.1 to test whether selectionSort works properly. The program requests up to 10 numbers (since the array is declared to be of size 10), stores them in the array num, calls selectionSort, then prints the sorted list.

Program P9.1

#include <stdio.h>

int main() {

void selectionSort(int [], int, int);

int v, num[10];

printf("Type up to 10 numbers followed by 0\n");

int n = 0;

scanf("%d", &v);

while (v != 0) {

num[n++] = v;

scanf("%d", &v);

}

//n numbers are stored from num[0] to num[n-1]

selectionSort(num, 0, n-1);

printf("\nThe sorted numbers are\n");

for (int h = 0; h < n; h++) printf("%d ", num[h]);

printf("\n");

} //end main

void selectionSort(int list[], int lo, int hi) {

//sort list[lo] to list[hi] in ascending order

int getSmallest(int [], int, int);

void swap(int [], int, int);

for (int h = lo; h < hi; h++) {

int s = getSmallest(list, h, hi);

swap(list, h, s);

}

} //end selectionSort

int getSmallest(int num[], int lo, int hi) {

//find position of smallest from num[lo] to num[hi]

int small = lo;

for (int h = lo + 1; h <= hi; h++)

if (num[h] < num[small]) small = h;

return small;

} //end getSmallest

void swap(int num[], int i, int j) {

//swap elements num[i] and num[j]

int hold = num[i];

num[i] = num[j];

num[j] = hold;

} //end swap

The following is a sample run of the program:

Type up to 10 numbers followed by 0

57 48 79 65 15 33 52 0

The sorted numbers are

15 33 48 52 57 65 79

Comments on Program P9.1

The program illustrates how to read and store an unknown amount of values in an array. The program caters for up to 10 numbers but must work if fewer numbers are supplied. We use n to subscript the array and to count the numbers. Initially, n is 0. The following describes what happens with the sample data:

§ The 1st number, 57, is read; it is not 0 so we enter the while loop. We store 57 in num[0] then add 1 to n, making it 1; one number has been read and n is 1.

§ The 2nd number, 48, is read; it is not 0 so we enter the while loop. We store 48 in num[1] then add 1 to n, making it 2; two numbers have been read and n is 2.

§ The 3rd number, 79, is read; it is not 0 so we enter the while loop. We store 79 in num[2] then add 1 to n, making it 3; three numbers have been read and n is 3.

§ The 4th number, 65, is read; it is not 0 so we enter the while loop. We store 65 in num[3] then add 1 to n, making it 4; four numbers have been read and n is 4.

§ The 5th number, 15, is read; it is not 0 so we enter the while loop. We store 15 in num[4] then add 1 to n, making it 5; five numbers have been read and n is 5.

§ The 6th number, 33, is read; it is not 0 so we enter the while loop. We store 33 in num[5] then add 1 to n, making it 6; six numbers have been read and n is 6.

§ The 7th number, 52, is read; it is not 0 so we enter the while loop. We store 52 in num[6] then add 1 to n, making it 7; seven numbers have been read and n is 7.

§ The 8th number, 0, is read; it is 0 so we exit the while loop and the array looks like this:

§

num
57	48	79	65	15	33	52
0	1	2	3	4	5	6

At any stage, the value of n indicates how many numbers have been stored up to that point. At the end, n is 7 and seven numbers have been stored in the array. The rest of the program can assume that n gives the number of values actually stored in the array; the values are stored from num[0] to num[n-1].

For example, the call

selectionSort(num, 0, n-1);

is a request to sort num[0] to num[n-1] but, since n is 7, it is a request to sort num[0] to num[6].

As written, the program will crash if the user enters more than 10 numbers before typing 0. When the 11^th number is read, an attempt will be made to store it in num[10], which does not exist, giving an “array subscript” error.

We can handle this by changing the while condition to this:

while (v != 0 && n < 10)

Now, if n reaches 10, the loop is not entered (since 10 is not less than 10) and no attempt will be made to store the 11^th number. Indeed, all numbers after the 10th one will be ignored.

As usual, it is best to use a symbolic constant (MaxNum, say) set to 10, and use MaxNum, rather than the constant 10, throughout the program.

We have sorted an array in ascending order. We can sort num[0] to num[n-1] in descending order with the following algorithm:

for h = 0 to n - 2

b = position of biggest number from num[h] to num[n-1]

swap num[h] and num[b]

endfor

We urge you to try Exercises 1 and 2 to print the results of the voting problem in ascending order by name and descending order by votes received.

9.2.1 Analysis of Selection Sort

To find the smallest of k items, we make k-1 comparisons. On the first pass, we make n-1 comparisons to find the smallest of n items. On the second pass, we make n-2 comparisons to find the smallest of n-1 items. And so on, until the last pass where we make one comparison to find the smaller of two items. In general, on the ith pass, we make n-i comparisons to find the smallest of n-i+1 items. Hence:

Total number of comparisons = 1 + 2 + ...+ n-1

= ½ n(n-1) ≈ ½ n²

We say selection sort is of order O(n²) (“big O n squared”). The constant ½ is not important in “big O” notation since, as n gets very big, the constant becomes insignificant.

On each pass, we swap two items using three assignments. We make n-1 passes so we make 3(n-1) assignments in all. Using “big O” notation, we say that the number of assignments is O(n). The constants 3 and 1 are not important as n gets large.

Does selection sort perform any better if there is order in the data? No. One way to find out is to give it a sorted list and see what it does. If you work through the algorithm, you will see that the method is oblivious to order in the data. It will make the same number of comparisons every time, regardless of the data.

As an exercise, modify the programming code so that it counts the number of comparisons and assignments made in sorting a list using selection sort.

9.3 Insertion Sort

Consider the same array as before:

num
57	48	79	65	15	33	52
0	1	2	3	4	5	6

Think of the numbers as cards on a table and picked up one at a time in the order in which they appear in the array. Thus, we first pick up 57, then 48, then 79, and so on, until we pick up 52. However, as we pick up each new number, we add it to our hand in such a way that the numbers in our hand are all sorted.

When we pick up 57, we have just one number in our hand. We consider one number to be sorted.

When we pick up 48, we add it in front of 57 so our hand contains

48 57

When we pick up 79, we place it after 57 so our hand contains

48 57 79

When we pick up 65, we place it after 57 so our hand contains

48 57 65 79

At this stage, four numbers have been picked up and our hand contains them in sorted order.

When we pick up 15, we place it before 48 so our hand contains

15 48 57 65 79

When we pick up 33, we place it after 15 so our hand contains

15 33 48 57 65 79

Finally, when we pick up 52, we place it after 48 so our hand contains

15 33 48 52 57 65 79

The numbers have been sorted in ascending order.

The method described illustrates the idea behind insertion sort. The numbers in the array will be processed one at a time, from left to right. This is equivalent to picking up the numbers from the table, one at a time. Since the first number, by itself, is sorted, we will process the numbers in the array starting from the second.

When we come to process num[h], we can assume that num[0] to num[h-1] are sorted. We then attempt to insert num[h] among num[0] to num[h-1] so that num[0] to num[h] are sorted. We will then go on to process num[h+1]. When we do so, our assumption that elements num[0] to num[h] are sorted will be true.

Sorting num in ascending order using insertion sort proceeds as follows:

1^st pass

§ Process num[1], that is, 48. This involves placing 48 so that the first two numbers are sorted; num[0] and num[1] now contain the following:

§

num
48	57
0	1

§ The rest of the array remains unchanged.

2^nd pass

§ Process num[2], that is, 79. This involves placing 79 so that the first three numbers are sorted; num[0] to num[2] now contain the following:

§

num
48	57	79
0	1	2

· The rest of the array remains unchanged.

3^rd pass

§ Process num[3], that is, 65. This involves placing 65 so that the first four numbers are sorted; num[0] to num[3] now contain the following:

§

num
48	57	65	79
0	1	2	3

· The rest of the array remains unchanged.

4^th pass

§ Process num[4], that is, 15. This involves placing 15 so that the first five numbers are sorted. To simplify the explanation, think of 15 as being taken out and stored in a simple variable (key, say) leaving a “hole” in num[4]. We can picture this as follows:

§

key		num
15		48	57	65	79		33	52
		0	1	2	3	4	5	6

§ The insertion of 15 in its correct position proceeds as follows:

§ Compare 15 with 79; it is smaller, so move 79 to location 4, leaving location 3 free. This gives the following:

§

key		num
15		48	57	65		79	33	52
		0	1	2	3	4	5	6

§ Compare 15 with 65; it is smaller, so move 65 to location 3, leaving location 2 free. This gives the following:

§

key		num
15		48	57		65	79	33	52
		0	1	2	3	4	5	6

§ Compare 15 with 57; it is smaller, so move 57 to location 2, leaving location 1 free. This gives the following:

§

key		num
15		48		57	65	79	33	52
		0	1	2	3	4	5	6

§ Compare 15 with 48; it is smaller, so move 48 to location 1, leaving location 0 free. This gives the following:

§

key		num
15			48	57	65	79	33	52
		0	1	2	3	4	5	6

§ There are no more numbers to compare with 15, so it is inserted in location 0, giving the following:

§

key		num
15		15	48	57	65	79	33	52
		0	1	2	3	4	5	6

§ We can express the logic of placing 15 (key) by comparing it with the numbers to its left, starting with the nearest one. As long as key is less than num[k], for some k, we move num[k] to position num[k+1] and move on to consider num[k-1], providing it exists. It won’t exist when k is actually 0. In this case, the process stops, and key is inserted in position 0.

5^th pass

§ Process num[5], that is, 33. This involves placing 33 so that the first six numbers are sorted. This is done as follows:

§ Store 33 in key, leaving location 5 free.

§ Compare 33 with 79; it is smaller, so move 79 to location 5, leaving location 4 free.

§ Compare 33 with 65; it is smaller, so move 65 to location 4, leaving location 3 free.

§ Compare 33 with 57; it is smaller, so move 57 to location 3, leaving location 2 free.

§ Compare 33 with 48; it is smaller, so move 48 to location 2, leaving location 1 free.

§ Compare 33 with 15; it is bigger, so insert 33 in location 1. This gives the following:

§

key		num
33		15	33	48	57	65	79	52
		0	1	2	3	4	5	6

· We can express the logic of placing 33 by comparing it with the numbers to its left, starting with the nearest one. As long as key is less than num[k], for some k, we move num[k] to position num[k+1] and move on to consider num[k-1], providing it exists. If key is greater than or equal to num[k] for some k, then key is inserted in position k+1. Here, 33 is greater than num[0] and so is inserted into num[1].

6^th pass

§ Process num[6], that is, 52. This involves placing 52 so that the first seven (all) numbers are sorted. This is done as follows:

§ Store 52 in key, leaving location 6 free.

§ Compare 52 with 79; it is smaller, so move 79 to location 6, leaving location 5 free.

§ Compare 52 with 65; it is smaller, so move 65 to location 5, leaving location 4 free.

§ Compare 52 with 57; it is smaller, so move 57 to location 4, leaving location 3 free.

§ Compare 52 with 48; it is bigger, so insert 52 in location 3. This gives the following:

§

key		num
33		15	33	48	52	57	65	79
		0	1	2	3	4	5	6

The array is now completely sorted.

The following is an outline to sort the first n elements of an array, num, using insertion sort:

for h = 1 to n - 1 do

insert num[h] among num[0] to num[h-1] so that

num[0] to num[h] are sorted

endfor

Using this outline, we write the function insertionSort using the parameter list.

void insertionSort(int list[], int n) {

//sort list[0] to list[n-1] in ascending order

for (int h = 1; h < n; h++) {

int key = list[h];

int k = h - 1; //start comparing with previous item

while (k >= 0 && key < list[k]) {

list[k + 1] = list[k];

--k;

}

list[k + 1] = key;

} //end for

} //end insertionSort

The while statement is at the heart of the sort. It states that as long as we are within the array (k >= 0) and the current number (key) is less than the one in the array (key < list[k]), we move list[k] to the right (list[k+1] = list[k]) and move on to the next number on the left (--k).

We exit the while loop if k is equal to -1 or if key is greater than or equal to list[k], for some k. In either case, key is inserted into list[k+1]. If k is -1, it means that the current number is smaller than all the previous numbers in the list and must be inserted in list[0]. But list[k+1] is list[0] when k is -1, so key is inserted correctly in this case.

The function sorts in ascending order. To sort in descending order, all we have to do is change < to > in the while condition, thus:

while (k >= 0 && key > list[k])

Now, a key moves to the left if it is bigger.

We write Program P9.2 to test whether insertionSort works correctly.

Program P9.2

#include <stdio.h>

int main() {

void insertionSort(int [], int);

int v, num[10];

printf("Type up to 10 numbers followed by 0\n");

int n = 0;

scanf("%d", &v);

while (v != 0) {

num[n++] = v;

scanf("%d", &v);

}

//n numbers are stored from num[0] to num[n-1]

insertionSort(num, n);

printf("\nThe sorted numbers are\n");

for (int h = 0; h < n; h++) printf("%d ", num[h]);

printf("\n");

} //end main

void insertionSort(int list[], int n) {

//sort list[0] to list[n-1] in ascending order

for (int h = 1; h < n; h++) {

int key = list[h];

int k = h - 1; //start comparing with previous item

while (k >= 0 && key < list[k]) {

list[k + 1] = list[k];

--k;

}

list[k + 1] = key;

} //end for

} //end insertionSort

The program requests up to 10 numbers (since the array is declared to be of size 10), stores them in the array num, calls insertionSort, then prints the sorted list. The following is a sample run of P9.2:

Type up to 10 numbers followed by 0

57 48 79 65 15 33 52 0

The sorted numbers are

15 33 48 52 57 65 79

9.3.1 Analysis of Insertion Sort

In processing item j, we can make as few as one comparison (if num[j] is bigger than num[j-1]) or as many as j-1 comparisons (if num[j] is smaller than all the previous items). For random data, it is expected that we would make ½(j-1) comparisons, on average. Hence, the average total number of comparisons to sort n items is as follows:

n
Σ
j=2 ½(j - 1) = ½ {1 + 2 + ...+ n-1} = ¼ n(n-1) ≈ ¼ n²

We say insertion sort is of order O(n²) (“big O n squared”). The constant ¼ is not important as n gets large.

Each time we make a comparison, we also make an assignment. Hence, the total number of assignments is also ¼ n(n-1) ≈ ¼ n².

We emphasize that this is an average for random data. Unlike selection sort, the actual performance of insertion sort depends on the data supplied. If the given array is already sorted, insertion sort will quickly determine this by making n-1 comparisons. In this case, it runs in O(n) time. One would expect that insertion sort will perform better the more order there is in the data.

If the given data is in descending order, insertion sort performs at its worst since each new number has to travel all the way to the beginning of the list. In this case, the number of comparisons is ½ n(n-1) ≈ ½ n². The number of assignments is also ½ n(n-1) ≈ ½ n².

Thus, the number of comparisons made by insertion sort ranges from n-1 (best) to ¼ n² (average) to ½ n² (worst). The number of assignments is always the same as the number of comparisons.

As an exercise, modify the programming code so that it counts the number of comparisons and assignments made in sorting a list using insertion sort.

9.3.2 Insert an Element in Place

Insertion sort uses the idea of adding a new element to an already sorted list so that the list remains sorted. We can treat this as a problem in its own right (nothing to do with insertion sort). Specifically, given a sorted list of items from list[m] to list[n], we want to add a new item (newItem, say) to the list so that list[m] to list[n+1] are sorted.

Adding a new item increases the size of the list by 1. We assume that the array has room to hold the new item. We write the function insertInPlace to solve this problem.

void insertInPlace(int newItem, int list[], int m, int n) {

//list[m] to list[n] are sorted

//insert newItem so that list[m] to list[n+1] are sorted

int k = n;

while (k >= m && newItem < list[k]) {

list[k + 1] = list[k];

--k;

}

list[k + 1] = newItem;

} //end insertInPlace

Now that we have insertInPlace, we can rewrite insertionSort (calling it insertionSort2) as follows:

void insertionSort2(int list[], int lo, int hi) {

//sort list[lo] to list[hi] in ascending order

void insertInPlace(int, int [], int, int);

for (int h = lo + 1; h <= hi; h++)

insertInPlace(list[h], list, lo, h - 1);

} //end insertionSort2

Note that the prototype for insertionSort2 is now this:

void insertionSort2(int [], int, int);

and to sort an array num of n items, we must call it like this:

insertionSort2(num, 0, n-1);

9.4 Sort an Array of Strings

Consider the problem of sorting a list of names in alphabetical order. We have seen that, in C, each name is stored in a character array. To store several names, we need a two-dimensional character array. For example, consider the following list of names.

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

0

S

a

m

l

a

l

,

R

a

w

l

e

\0

1

W

i

l

l

i

a

m

s

,

M

a

r

k

\0

2

D

e

l

w

i

n

,

M

a

c

\0

3

T

a

y

l

o

r

,

V

i

c

t

o

r

\0

4

M

o

h

a

m

e

d

,

A

b

u

\0

5

S

i

n

g

h

,

K

r

i

s

h

n

a

\0

6

T

a

w

a

r

i

,

T

a

u

\0

7

A

b

d

o

o

l

,

Z

a

i

d

\0

To store this list, we will require a declaration such as the following:

char list[8][15];

To cater for longer names, we can increase 15, and to cater for more names, we can increase 8.

The process of sorting list is essentially the same as sorting an array of integers. The major difference is that whereas we use < to compare two numbers, we must use strcmp to compare two names. In the function insertionSortshown earlier, the while condition changes from this:

while (k >= lo && key < list[k])

to the following, where key is now declared as char key[15]:

while (k >= lo && strcmp(key, list[k]) < 0)

Also, we must now use strcpy (since we can’t use = for strings) to assign a name to another location. We will see the complete function in the next section.

9.4.1 Variable-Length Arrays

We will use this example to show how variable-length arrays (VLAs) may be used in C. This feature is available only in C versions from C99 and later. The idea is that the size of an array may be specified at run-time as opposed to compile-time.

In the function below, note the declaration of list (char list[][max]) in the parameter list. The size of the first dimension is left unspecified, as for one-dimensional arrays. The size of the second dimension is specified using the parameter max; the value of max will be specified when the function is called. This gives us a bit more flexibility since we can specify the size of the second dimension at run time.

void insertionSort3(int lo, int hi, int max, char list[][max]) {

//Sort the strings in list[lo] to list[hi] in alphabetical order.

//The maximum string size is max - 1 (one char taken up by \0).

char key[max];

for (int h = lo + 1; h <= hi; h++) {

strcpy(key, list[h]);

int k = h - 1; //start comparing with previous item

while (k >= lo && strcmp(key, list[k]) < 0) {

strcpy(list[k + 1], list[k]);

--k;

}

strcpy(list[k + 1], key);

} //end for

} // end insertionSort3

We write a simple main routine to test insertionSort3 as shown in Program P9.3.

Program P9.3

#include <stdio.h>

#include <string.h>

#define MaxNameSize 14

#define MaxNameBuffer MaxNameSize+1

#define MaxNames 8

int main() {

void insertionSort3(int, int, int max, char [][max]);

char name[MaxNames][MaxNameBuffer] =

{"Samlal, Rawle", "Williams, Mark","Delwin, Mac",

"Taylor, Victor", "Mohamed, Abu","Singh, Krishna",

"Tawari, Tau", "Abdool, Zaid" };

insertionSort3(0, MaxNames-1, MaxNameBuffer, name);

printf("\nThe sorted names are\n\n");

for (int h = 0; h < MaxNames; h++) printf("%s\n", name[h]);

} //end main

void insertionSort3(int lo, int hi, int max, char list[][max]) {

//Sort the strings in list[lo] to list[hi] in alphabetical order.

//The maximum string size is max - 1 (one char taken up by \0).

char key[max];

for (int h = lo + 1; h <= hi; h++) {

strcpy(key, list[h]);

int k = h - 1; //start comparing with previous item

while (k >= lo && strcmp(key, list[k]) < 0) {

strcpy(list[k + 1], list[k]);

--k;

}

strcpy(list[k + 1], key);

} //end for

} // end insertionSort3

The declaration of name initializes it with the eight names shown earlier. When run, the program produces the following output:

The sorted names are

Abdool, Zaid

Delwin, Mac

Mohamed, Abu

Samlal, Rawle

Singh, Krishna

Tawari, Tau

Taylor, Victor

Williams, Mark

9.5 Sort Parallel Arrays

It is quite common to have related information in different arrays. For example, suppose, in addition to name, we have an integer array id such that id[h] is an identification number associated with name[h], as shown here.

It is quite common to have related information in different arrays. For example, suppose, in addition to name, we have an integer array id such that id[h] is an identification number associated with name[h], as shown here.

	name	id
0	Samlal, Rawle	8742
1	Williams, Mark	5418
2	Delwin, Mac	4833
3	Taylor, Victor	4230
4	Mohamed, Abu	8583
5	Singh, Krishna	2458
6	Tawari, Tau	5768
7	Abdool, Zaid	7746

Consider the problem of sorting the names in alphabetical order. At the end, we would want each name to have its correct ID number. So, for example, after the sorting is done, name[0] should contain Abdool, Zaid and id[0] should contain 7746.

To achieve this, each time a name is moved during the sorting process, the corresponding ID number must also be moved. Since the name and ID number must be moved “in parallel,” we say we are doing a parallel sort or we are sorting parallel arrays.

We rewrite insertionSort3 to illustrate how to sort parallel arrays. We simply add the code to move an ID whenever a name is moved. We call it parallelSort.

void parallelSort(int lo, int hi, int max, char list[][max], int id[]) {

//Sort the names in list[lo] to list[hi] in alphabetical order, ensuring

//that each name remains with its original id number.

//The maximum string size is max - 1 (one char taken up by \0).

char key[max];

for (int h = lo + 1; h <= hi; h++) {

strcpy(key, list[h]);

int m = id[h]; // extract the id number

int k = h - 1; //start comparing with previous item

while (k >= lo && strcmp(key, list[k]) < 0) {

strcpy(list[k + 1], list[k]);

id[k+ 1] = id[k]; // move up id when we move a name

--k;

}

strcpy(list[k + 1], key);

id[k + 1] = m; // store id in the same position as the name

} //end for

} //end parallelSort

We test parallelSort by writing the following main routine:

#include <stdio.h>

#include <string.h>

#define MaxNameSize 14

#define MaxNameBuffer MaxNameSize+1

#define MaxNames 8

int main() {

void parallelSort(int, int, int max, char [][max], int[]);

char name[MaxNames][MaxNameBuffer] =

{"Samlal, Rawle", "Williams, Mark","Delwin, Mac",

"Taylor, Victor", "Mohamed, Abu","Singh, Krishna",

"Tawari, Tau", "Abdool, Zaid" };

int id[MaxNames] = {8742,5418,4833,4230,8583,2458,5768,3313};

parallelSort(0, MaxNames-1, MaxNameBuffer, name, id);

printf("\nThe sorted names and IDs are\n\n");

for (int h = 0; h < MaxNames; h++)

printf("%-18s %d\n", name[h], id[h]);

} //end main

When run, it produces the following output:

The sorted names and IDs are
Abdool, Zaid	7746
Delwin, Mac	4833
Mohamed, Abu	8583
Samlal, Rawle	8742
Singh, Krishna	2458
Tawari, Tau	5768
Taylor, Victor	4230
Williams, Mark	5418

We note, in passing, that "parallel arrays" can be more conveniently stored using C structures. However, this topic is beyond the scope of this book.

9.6 Binary Search

Binary search is a very fast method for searching a list of items for a given one, providing the list is sorted (either ascending or descending). To illustrate the method, consider a list of 11 numbers, sorted in ascending order.

num
17	24	31	39	44	49	56	66	72	78	83
0	1	2	3	4	5	6	7	8	9	10

Suppose we wish to search for 56. The search proceeds as follows:

§ First, we find the middle item in the list. This is 49 in position 5. We compare 56 with 49. Since 56 is bigger, we know that if 56 is in the list, it must be after position 5, since the numbers are in ascending order. In our next step, we confine our search to locations 6 to 10.

§ Next, we find the middle item from locations 6 to 10. This is the item in location 8, that is, 72.

§ We compare 56 with 72. Since 56 is smaller, we know that if 56 is in the list, it must be before position 8, since the numbers are in ascending order. In our next step, we confine our search to locations 6 to 7.

§ Next, we find the middle item from locations 6 to 7. In this case, we can choose either item 6 or item 7. The algorithm we will write will choose item 6, that is, 56.

§ We compare 56 with 56. Since they are the same, our search ends successfully, finding the required item in position 6.

Suppose we were searching for 60. The search will proceed as above until we compare 60 with 56 (in location 6).

§ Since 60 is bigger, we know that if 60 is in the list, it must be after position 6, since the numbers are in ascending order. In our next step, we confine our search to locations 7 to 7. This is just one location.

§ We compare 60 with item 7, that is, 66. Since 60 is smaller, we know that if 60 is in the list, it must be before position 7. Since it can’t be after position 6 and before position 7, we conclude that it is not in the list.

At each stage of the search, we confine our search to some portion of the list. Let us use the variables lo and hi as the subscripts which define this portion. In other words, our search will be confined to the numbers from num[lo] to num[hi], inclusive.

Initially, we want to search the entire list so that we will set lo to 0 and hi to 10, in this example.

How do we find the subscript of the middle item? We will use the calculation

mid = (lo + hi) / 2;

Since integer division will be performed, the fraction, if any, is discarded. For example when lo is 0 and hi is 10, mid becomes 5; when lo is 6 and hi is 10, mid becomes 8; and when lo is 6 and hi is 7, mid ecomes 6.

As long as lo is less than or equal to hi, they define a non-empty portion of the list to be searched. When lo is equal to hi, they define a single item to be searched. If lo ever gets bigger than hi, it means we have searched the entire list and the item was not found.

Based on these ideas, we can now write a function binarySearch. To be more general, we will write it so that the calling routine can specify which portion of the array it wants the search to look for the item.

Thus, the function must be given the item to be searched for (key), the array (list), the start position of the search (lo) and the end position of the search (hi). For example, to search for the number 56 in the array num, above, we can issue the following call:

binarySearch(56, num, 0, 10)

The function must tell us the result of the search. If the item is found, the function will return its location. If not found, it will return -1.

int binarySearch(int key, int list[], int lo, int hi) {

//search for key from list[lo] to list[hi]

//if found, return its location; otherwise, return -1

int mid;

while (lo <= hi) {

mid = (lo + hi) / 2;

if (key == list[mid]) return mid; // found

if (key < list[mid]) hi = mid - 1;

else lo = mid + 1;

}

return -1; //lo and hi have crossed; key not found

} //end binarySearch

If item contains a number to be searched for, we can write the following code to call binarySearch and check the result of the search:

int ans = binarySearch(item, num, 0, 12);

if (ans == -1) printf(“%d not found\n”, item);

else printf(“%d found in location %d\n”, item, ans);

If we wish to search for item from locations i to j, we can write this:

int ans = binarySearch(item, num, i, j);

9.7 Word Frequency Count

Let’s write a program to read an English passage and count the number of times each word appears. The output consists of an alphabetical listing of the words and their frequencies.

We can use the following outline to develop our program:

while there is input

get a word

search for word

if word is in the table

add 1 to its count

else

add word to the table

set its count to 1

endif

endwhile

print table

This is a typical “search and insert” situation. We search for the next word among the words stored so far. If the search succeeds, we need only increment its count. If the search fails, the word is put in the table, and its count set to 1.

A major design decision here is how to search the table, which, in turn, will depend on where and how a new word is inserted in the table. The following are two possibilities:

1. A new word is inserted in the next free position in the table. This implies that a sequential search must be used to look for an incoming word since the words would not be in any particular order. This method has the advantages of simplicity and easy insertion, but searching takes longer as more words are put in the table.

2. A new word is inserted in the table in such a way that the words are always in alphabetical order. This may entail moving words that have already been stored so that the new word may be slotted in the right place. However, since the table is in order, a binary search can be used to search for an incoming word.

3. For this method, searching is faster, but insertion is slower than in (1). Since, in general, searching is done more frequently than inserting, (2) might be preferable.

Another advantage of (2) is that, at the end, the words will already be in alphabetical order and no sorting will be required. If (1) is used, the words will need to be sorted to obtain the alphabetical order.

We will write our program using the approach in (2). The complete program is shown as Program P9.4.

Program P9.4

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <stdlib.h>

#define MaxWords 50

#define MaxLength 10

#define MaxWordBuffer MaxLength+1

int main() {

int getWord(FILE *, char[]);

int binarySearch(int, int, char [], int max, char [][max]);

void addToList(char[], int max, char [][max], int[], int, int);

void printResults(FILE *, int max, char [][max], int[], int);

char wordList[MaxWords][MaxWordBuffer], word[MaxWordBuffer];

int frequency[MaxWords], numWords = 0;

FILE * in = fopen("passage.txt", "r");

if (in == NULL){

printf("Cannot find file\n");

exit(1);

}

FILE * out = fopen("output.txt", "w");

if (out == NULL){

printf("Cannot create output file\n");

exit(2);

}

for (int h = 1; h <= MaxWords ; h++) frequency[h] = 0;

while (getWord(in, word) != 0) {

int loc = binarySearch (0, numWords-1, word, MaxWordBuffer,

wordList);

if (strcmp(word, wordList[loc]) == 0)

++frequency[loc]; //word found

else //this is a new word

if (numWords < MaxWords) { //if table is not full

addToList(word, MaxWordBuffer, wordList, frequency, loc,

numWords-1);

++numWords;

}

else fprintf(out, "'%s' not added to table\n", word);

}

printResults(out, MaxWordBuffer, wordList, frequency, numWords);

} // end main

int getWord(FILE * in, char str[]) {

// store the next word, if any, in str; convert word to lowercase

// return 1 if a word is found; 0, otherwise

char ch;

int n = 0;

// read over white space

while (!isalpha(ch = getc(in)) && ch != EOF) ; //empty while body

if (ch == EOF) return 0;

str[n++] = tolower(ch);

while (isalpha(ch = getc(in)) && ch != EOF)

if (n < MaxLength) str[n++] = tolower(ch);

str[n] = '\0';

return 1;

} // end getWord

int binarySearch(int lo, int hi, char key[], int max, char list[][max]) {

//search for key from list[lo] to list[hi]

//if found, return its location;

//if not found, return the location in which it should be inserted

//the calling program will check the location to determine if found

while (lo <= hi) {

int mid = (lo + hi) / 2;

int cmp = strcmp(key, list[mid]);

if (cmp == 0) return mid; // found

if (cmp < 0) hi = mid - 1;

else lo = mid + 1;

}

return lo; //not found; should be inserted in location lo

} //end binarySearch

void addToList(char item[], int max, char list[][max],

int freq[], int p, int n) {

//adds item in position list[p]; sets freq[p] to 1

//shifts list[n] down to list[p] to the right

for (int h = n; h >= p; h--) {

strcpy(list[h+1], list[h]);

freq[h+1] = freq[h];

}

strcpy(list[p], item);

freq[p] = 1;

} //end addToList

void printResults(FILE *out, int max, char list[][max],

int freq[], int n) {

fprintf(out, "\nWords Frequency\n\n");

for (int h = 0; h < n; h++)

fprintf(out, "%-15s %2d\n", list[h], freq[h]);

} //end printResults

Suppose the file passage.txt contains the following data (from If by Rudyard Kipling):

If you can dream—and not make dreams your master;

If you can think—and not make thoughts your aim;

If you can meet with Triumph and Disaster

And treat those two impostors just the same...

If you can fill the unforgiving minute

With sixty seconds’ worth of distance run,

Yours is the Earth...

When Program P9.4 was run with this data, it produced the following output:

Words	Frequency
aim	1
and	4
can	4
disaster	1
distance	1
dream	1
dreams	1
earth	1
fill	1
if	4
imposters	1
is	1
just	1
make	2
master	1
meet	1
minute	1
not	2
of	1
run	1
same	1
seconds	1
sixty	1
the	3
think	1
those	1
thoughts	1
treat	1
triumph	1
two	1
unforgivin	1
with	2
worth	1
you	4
your	2
yours	1

Comments on Program P9.4

§ For our purposes, we assume that a word begins with a letter and consists of letters only. If you want to include other characters (such as a hyphen or apostrophe), you need change only the getWord function.

§ MaxWords denotes the maximum number of distinct words catered for. For testing the program, we have used 50 for this value. If the number of distinct words in the passage exceeds MaxWords (50, say), any words after the 50^th will be read but not stored, and a message to that effect will be printed. However, the count for a word already stored will be incremented if it is encountered again.

§ MaxLength (we use 10 for testing) denotes the maximum length of a word. Strings are declared using MaxLength+1 (defined as MaxWordBuffer) to cater for \0, which must be added at the end of each string.

§ main checks that the input file exists and that the output file can be created. Next, it initializes the frequency counts to 0. It then processes the words in the passage based on the outline shown at the beginning of this Section.

§ getWord reads the input file and stores the next word found in its string argument. It returns 1 if a word is found and 0, otherwise. If a word is longer than MaxLength, only the first MaxLength letters are stored; the rest are read and discarded. For example, unforgiving is truncated to unforgivin using a word size of 10.

§ All words are converted to lowercase so that, for instance, The and the are counted as the same word.

§ We wrote binarySearch so that if the word is found, its location (loc, say) is returned. If not found, the location in which the word should be inserted is returned. The test

§ if (strcmp(word, wordList[loc]) == 0)

§ determines whether it was found. addToList is given the location in which to insert a new word. Words to the right of, and including, this location are shifted to make room for the new word.

§ In declaring a function prototype, some compilers allow a two-dimensional array parameter to be declared as in char [][], with no size specified for either dimension. Others require that the size of the second dimension must be specified. Specifying the size of the second dimension should work on all compilers. In our program, we specify the second dimension using the parameter max, whose value will be supplied when the function is called.

9.8 Merge Sorted Lists

Merging is the process by which two or more ordered lists are combined into one ordered list. For example, given two lists of numbers, A and B, as follows:

A: 21 28 35 40 61 75

B: 16 25 47 54

They can be combined into one ordered list, C, as follows:

C: 16 21 25 28 35 40 47 54 61 75

The list C contains all the numbers from lists A and B. How can the merge be performed?

One way to think about it is to imagine that the numbers in the given lists are stored on cards, one per card, and the cards are placed face up on a table, with the smallest at the top. We can imagine the lists A and B as follows:

21 16

28 25

35 47

40 54

61

75

We look at the top two cards, 21 and 16. The smaller, 16, is removed and placed in C. This exposes the number 25. We have this:

21 25

28 47

35 54

40

61

75

The top two cards are now 21 and 25. The smaller, 21, is removed and added to C, which now contains 16 21. This exposes the number 28. We have this:

28 25

35 47

40 54

61

75

The top two cards are now 28 and 25. The smaller, 25, is removed and added to C, which now contains 16 21 25. This exposes the number 47. We have this:

28 47

35 54

40

61

75

The top two cards are now 28 and 47. The smaller, 28, is removed and added to C, which now contains 16 21 25 28. This exposes the number 35. We have this:

35 47

40 54

61

75

The top two cards are now 35 and 47. The smaller, 35, is removed and added to C, which now contains 16 21 25 28 35. This exposes the number 40. We have this:

40 47

61 54

75

The top two cards are now 40 and 47. The smaller, 40, is removed and added to C, which now contains 16 21 25 28 35 40. This exposes the number 61. We have this:

61 47

75 54

The top two cards are now 61 and 47. The smaller, 47, is removed and added to C, which now contains 16 21 25 28 35 40 47. This exposes the number 54. We have this:

61 54

75

The top two cards are now 61 and 54. The smaller, 54, is removed and added to C, which now contains 16 21 25 28 35 40 47 54. The list B has no more numbers.

We copy the remaining elements (61 75) of A to C, which now contains the following:

16 21 25 28 35 40 47 54 61 75

The merge is now completed.

At each step of the merge, we compare the smallest remaining number of A ith the smallest remaining number of B. The smaller of these is added to C. If the smaller comes from A, we move on to the next number in A; if the smaller comes from B, we move on to the next number in B.

This is repeated until all the numbers in either A or B have been used. If all the numbers in A have been used, we add the remaining numbers from B to C. If all the numbers in B have been used, we add the remaining numbers from A to C.

We can express the logic of the merge as follows:

while (at least one number remains in both A and B) {

if (smallest in A < smallest in B)

add smallest in A to C

move on to next number in A

else

add smallest in B to C

move on to next number in B

endif

}

if (A has ended) add remaining numbers in B to C

else add remaining numbers in A to C

9.8.1 Implement the Merge

Assume that an array A contains m numbers stored in A[0] to A[m-1] and an array B contains n numbers stored in B[0] to B[n-1]. Assume that the numbers are stored in ascending order. We want to merge the numbers in A and B into another array C such that C[0] to C[m+n-1] contains all the numbers in A and B sorted in ascending order.

We will use integer variables i, j, and k to subscript the arrays A, B, and C, respectively. “Moving on to the next position” in an array can be done by adding 1 to the subscript variable. We can implement the merge with the following code:

i = 0; //i points to the first (smallest) number in A

j = 0; //j points to the first (smallest) number in B

k = -1; //k will be incremented before storing a number in C[k]

while (i < m && j < n) {

if (A[i] < B[j]) C[++k] = A[i++];

else C[++k] = B[j++];

}

if (i == m) //copy B[j] to B[n-1] to C

for ( ; j < n; j++) C[++k] = B[j];

else // j == n, copy A[i] to A[m-1] to C

for ( ; i < m; i++) C[++k] = A[i];

Program P9.5 shows a simple main function that tests the logic of our method. We write the merge as a function that, given the arguments A, m, B, n, and C, performs the merge and returns the number of elements, m+n, in C. When run, the program prints the contents of C, like this:

16 21 25 28 35 40 47 54 61 75

Program P9.5

#include <stdio.h>

int main () {

int merge(int[], int, int[], int, int[]);

int A[] = {21, 28, 35, 40, 61, 75};

int B[] = {16, 25, 47, 54};

int C[20];

int n = merge(A, 6 , B, 4, C);

for (int h = 0; h < n; h++) printf("%d ", C[h]);

printf("\n\n");

} //end main

int merge(int A[], int m, int B[], int n, int C[]) {

int i = 0; //i points to the first (smallest) number in A

int j = 0; //j points to the first (smallest) number in B

int k = -1; //k will be incremented before storing a number in C[k]

while (i < m && j < n) {

if (A[i] < B[j]) C[++k] = A[i++];

else C[++k] = B[j++];

}

if (i == m) ///copy B[j] to B[n-1] to C

for ( ; j < n; j++) C[++k] = B[j];

else // j == n, copy A[i] to A[m-1] to C

for ( ; i < m; i++) C[++k] = A[i];

return m + n;

} //end merge

As a matter of interest, we can also implement merge as follows:

int merge(int A[], int m, int B[], int n, int C[]) {

int i = 0; //i points to the first (smallest) number in A

int j = 0; //j points to the first (smallest) number in B

int k = -1; //k will be incremented before storing a number in C[k]

while (i < m || j < n) {

if (i == m) C[++k] = B[j++];

else if (j == n) C[++k] = A[i++];

else if (A[i] < B[j]) C[++k] = A[i++];

else C[++k] = B[j++];

}

return m + n;

} //end merge

The while loop expresses the following logic: as long as there is at least one element to process in either A or B, we enter the loop. If we are finished with A (i == m), copy an element from B to C. If we are finished with B (j == n), copy an element from A to C. Otherwise, copy the smaller of A[i] and B[j] to C. Each time we copy an element from an array, we add 1 to the subscript for that array.

While the previous version implements the merge in a straightforward way, it seems reasonable to say that this version is a bit neater.

EXERCISES 9

1. In the voting problem of Section 8.15, print the results in alphabetical order by candidate name. Hint: in sorting the name array, when you move a name, make sure and move the corresponding item in the vote array.

2. In the voting problem of Section 8.15, print the results in descending order by candidate score.

3. Write a function to sort a double array in ascending order using selection sort. Do the sort by finding the largest number on each pass.

4. Write a program to find out, for a class of students, the number of families with 1, 2, 3, ... up to 8 or more children. The data consists of the number of children in each pupil’s family, terminated by 0. Print the results in decreasing order by family-size popularity. That is, print the most popular family-size first and the least popular family-size last.

5. A survey of 10 pop artists is made. Each person votes for an artist by specifying the number of the artist (a value from 1 to 10). Write a program to read the names of the artists, followed by the votes, and find out which artist is the most popular. Choose a suitable end-of-data marker.

6. Print a table of the results with the most popular artist first and the least popular last.

7. The median of a set of n numbers (not necessarily distinct) is obtained by arranging the numbers in order and taking the number in the middle. If n is odd, there is a unique middle number. If n is even, then the average of the two middle values is the median. Write a program to read a set of n positive integers (assume n < 100) and print their median; n is not given but 0 indicates the end of the data.

8. The mode of a set of n numbers is the number which appears most frequently. For example, the mode of 7 3 8 5 7 3 1 3 4 8 9 is 3.

9. Write a program to read a set of n arbitrary positive integers (assume n < 100) and print their mode; n is not given but 0 indicates the end of the data.

10. Write an efficient program to find the mode if it is known that the numbers all lie between 1 and 999, inclusive, with no restriction on the amount of numbers supplied; 0 ends the data.

11. An array num contains k numbers in num[0] to num[k-1], sorted in descending order. Write a function insertInPlace which, given num, k and another number x, inserts x in its proper position such that num[0] to num[k] are sorted in descending order. Assume the array has room for x.

12. A multiple-choice examination consists of twenty questions. Each question has five choices, labelled A, B, C, D and E. The first line of data contains the correct answers to the twenty questions in the first 20 consecutive character positions, for example:

13. BECDCBAADEBACBAEDDBE

14. Each subsequent line contains the answers for a candidate. Data on a line consists of a candidate number (an integer), followed by one or more spaces, followed by the twenty answers given by the candidate in the next twenty consecutive character positions. An X is used if a candidate did not answer a particular question. You may assume all data are valid and stored in a file exam.dat. A sample line is:

15. 4325 BECDCBAXDEBACCAEDXBE

16. There are at most 100 candidates. A line containing a “candidate number” 0 only indicates the end of the data.

17. Points for a question are awarded as follows:– correct answer: 4 points; wrong answer: -1 point; no answer: 0 points.

18. Write a program to process the data and print a report consisting of candidate number and the total points obtained by the candidate, in ascending order by candidate number. At the end, print the average number of points gained by the candidates.

19. An array A contains integers that first increase in value and then decrease in value, for example:

20.

A
17	24	31	83	78	72	66	56	49	44	39
0	1	2	3	4	5	6	7	8	9	10

21. It is unknown at which point the numbers start to decrease. Write efficient code to copy the numbers from A to another array B so that B is sorted in ascending order. Your code must take advantage of the way the numbers are arranged in A. (Hint: perform a merge starting at both ends.)

22. You are given two integer arrays A and B each of maximum size 500. If A[0] contains m, say, then m numbers are stored in arbitrary order from A[1] to A[m]. If B[0] contains n, say, then n numbers are stored in arbitrary order from B[1] to B[n].

23. Write code to merge the elements of A and B into another array C such that C[0] ontains m+n and C[1] to C[m+n] contain the numbers in ascending order.

24. An anagram is a word or phrase formed by rearranging the letters of another word or phrase. Examples of one-word anagrams are: sister/resist and senator/treason. We can get more interesting anagrams if we ignore letter case and punctuation marks. Examples are: Time-table/Bet I'm Late, Clint Eastwood/Old West Action and Astronomers/No More Stars.

25. Write a function which, given two strings, returns 1 if the strings are anagrams of each other and 0 if they are not.

26. An input file contains one word or phrase per line. Write a program to read the file and output all words/phrases (from the file) that are anagrams of each other. Print a blank line between each group of anagrams.