Object-oriented programs deal with objects, which in turn consist of data and the methods of operating on that data. Although having objects all in a jumble often is fine, at other times it is convenient, or even required that the objects be given some sort of order. Perhaps you need to examine the objects in chronological order, by size, or in alphabetical order.
The job of imposing order on a group of objects or a set of data is called sorting. A number of techniques exist for sorting data, each of which may be optimized for some type of trait for example, ease of use, speed, or size. Today you will learn
Many books have been written on sorting algorithms, and most take what I would call an academic view of the subject. These books are filled with formulae showing that one sort or another is faster, and examining the mathematics of sorting.
All that is required for a practical approach, however, is to know how fast your sort is, and for what it is optimized. Sorts break down into slow, quick, and wicked-fast. In this book, I'll leave out the slow sorts, show you a few fast sorts, and then show you one or two wicked-fast sorts.
If you are interested in a more rigorous approach to the speed and efficiency of sorting (one that tells you how well the particular sort approximates the goal of N log(2) of N compares, where N is the number of elements to be sorted), I recommend Algorithms in C++ by Sedgewick as a good starting point.
One of the simplest sorts available is the selection sort. Like the insertion and bubble sorts, this is a reasonably fast sort, and it is easy to implement.
Imagine that you have a set of children's blocks in front of you, as shown in figure 4.1.
Figure 4.1. Blocks to sort.
Follow this technique: Separate the first block (x) from the others and call it the target. Of the remaining blocks, you can see that a is the smallest (earliest in the alphabet), so swap a with the target. That finishes round 1 of the sort, and your array looks like figure 4.2.
Figure 4.2. Blocks to sort after the first round.
For each subsequent round, start with the next block (in this case, r). Examine the remaining blocks and establish which is smallest; again, in this case, b. Once again, swap them; after round 2, the blocks will be in the order shown in figure 4.3.
Figure 4.3. Blocks to sort after the second round.
This process continues until the entire array is sorted. Listing 4.1 illustrates this technique.
Listing 4.1 Using a Selection Sort
1: // Listing 4.1 - Using a Selection Sort
2:
3: #include <iostream.h>
4: #include <string.h>
5:
6: void Swap( char *Array, int index1, int index2);
7: void SelectionSort(char *Array);
8:
9: int main()
10: {
11: char buffer[100];
12: cout << "Enter up to 100 characters: ";
13: cin.getline(buffer,100);
14: cout << "Unsorted:\t" << buffer << endl;
15: SelectionSort(buffer);
16: cout << "Sorted:\t\t" << buffer << endl;
17: return 0;
18: }
19:
20: // Read through each member of the array in turn
21: // For every member, examine every remaining member and
22: // swap with smallest
23: void SelectionSort(char *Array)
24: {
25: int ArrayLen = strlen(Array);
26: for (int i = 0; i<ArrayLen; i++)
27: {
28: int min = i;
29: for (int j = i+1; j< ArrayLen; j++)
30: if (Array[j] < Array[min])
31: min = j;
32: Swap(Array,min,i);
33: }
34: }
35:
36: void Swap( char *Array, int left, int right)
37: {
38: char tmp = Array[left];
39: Array[left]=Array[right];
40: Array[right]=tmp;
41: }
Output:
Enter up to 100 characters: jdk;ayf4eyiapuvhia;jfkda;jdajdjkewnzc
Unsorted: jdk;ayf4eyiapuvhia;jfkda;jdajdjkewnzc
Sorted: 4;;;aaaaacddddeeffhiijjjjjkkknpuvwyyz
Enter up to 100 characters: Eternal vigilance is the price of liberty
Unsorted: Eternal vigilance is the price of liberty
Sorted: Eaabcceeeeefghiiiiilllnnoprrrstttvy
Analysis:
The user is prompted, in line 12, to enter up to 100 characters. An array is created and passed to SelectionSort(), which ticks through each member of the array in the outer loop, as shown in line 26.
For each time through the loop, the smallest remaining element in the array is selected in the inner loop in lines 28 through 31. Swap() then is called to swap the smaller element into position.
Although this is an inefficient sort in many ways, it does work quickly on a modern computer and may be all you need for many sorts. Also, it has the advantage that every member of the array is filled with (at most) one swap, which works well when you are swapping large objects.
Note that the program was run twice, and the second time a number of spaces were introduced. These are all pushed to the front of the array, so in the sorted output there are seven spaces before the first letter. Capital letters evaluate to lower values than lowercase, so the first printable letter is the uppercase E, which does not sort in with the lowercase es.
The program in listing 4.1 calls swap on each member of the array. Careful examination reveals, however, that many times a swap is unnecessary; the current member of the array already is the smallest. Listing 4.2 illustrates how testing for this condition can reduce the number of calls to Swap and thus potentially improve the efficiency of the program.
Listing 4.2 Demonstrating Potential Optimization
1: // Listing 4.2 - Demonstrating Potential Optimization
2:
3: #include <iostream.h>
4: #include <string.h>
5:
6: void Swap( char *Array, int min, int i);
7: void SelectionSort(char *Array);
8: int NumberSwaps = 0;
9: int NumberExaminations = 0;
10: int WouldSwap=0;
11:
12: int main()
13: {
14: char buffer[100];
15: cout << "Enter up to 100 characters: ";
16: cin.getline(buffer,100);
17: cout << "Unsorted:\t" << buffer << endl;
18: SelectionSort(buffer);
19: cout << "Sorted:\t\t" << buffer << endl;
20:
21: cout << "\nExamined: " << NumberExaminations;
22: cout << " Would Swap: " << WouldSwap << endl;
23: cout << " Did Swap: " << NumberSwaps;
24:
25:
26: return 0;
27: }
28:
29: enum BOOL {FALSE, TRUE};
30: // Read through each member of the array in turn
31: // For every member, examine every remaining member and
32: // swap with smallest
33: void SelectionSort(char *Array)
34: {
35: int ArrayLen = strlen(Array);
36: for (int i = 0; i<ArrayLen; i++)
37: {
38: int min = i;
39: for (int j = i+1; j< ArrayLen; j++)
40: {
41: NumberExaminations++;
42:
43: if (Array[j] < Array[min])
44: min = j;
45: }
46: WouldSwap++;
47: if (i != min)
48: {
49: NumberSwaps++;
50: Swap(Array,min,i);
51: }
52: }
53: }
54:
55: void Swap( char *Array, int min, int i)
56: {
57: char tmp = Array[min];
58: Array[min]=Array[i];
59: Array[i]=tmp;
60: }
Output:
Enter up to 100 characters: jdk;ayf4eyiapuvhia;jfkda;jdajdjkewnzc
Unsorted: jdk;ayf4eyiapuvhia;jfkda;jdajdjkewnzc
Sorted: 4;;;aaaaacddddeeffhiijjjjjkkknpuvwyyz
Examined: 666 Would Swap: 37 Did Swap: 32
Enter up to 100 characters: Eternal vigilance is the price of liberty
Unsorted: Eternal vigilance is the price of liberty
Sorted: Eaabcceeeeefghiiiiilllnnoprrrstttvy
Examined: 820 Would Swap: 41 Did Swap: 38
Enter up to 100 characters: abcdefghijklmnopqrstuvwxyz
Unsorted: abcdefghijklmnopqrstuvwxyz
Sorted: abcdefghijklmnopqrstuvwxyz
Examined: 325 Would Swap: 26 Did Swap: 0
Analysis:
Listing 4.2 is much like listing 4.1, but some external counter variables are declared. Although externals are shunned in any large program, they are convenient in a quick-and-dirty demonstration like this.
NumberExaminations keeps track of how many letters are examined in the inner loop. WouldSwap keeps track of how many times Swap() would be called if there were no check to make sure that it is needed, and NumberSwaps keeps track of the actual count of calls to Swap().
The check on need is performed in line 47, by examining whether the conditions for the swap have been met. The variable i will be equal to min if no swap is needed; otherwise, a value to swap has been found.
As you can see, in an array that already is in order or nearly in order, this examination can reduce dramatically the number of swaps.
In the most extreme examination, where the original array was fully sorted before processing began, the number of swaps was reduced from 26 to 0. This appears to be a fantastic savings, because Swap() did not have to be called for any of its potential 26 function calls. The price, however, was 26 additional comparisons. Assuming that you made the Swap() function inline, it is not clear whether you have saved much, if anything, by adding these compares.
When it is time to optimize your program, as discussed on day 17, you will examine the actual assembler output of both the inline Swap() function and the comparison to really determine which version is more efficient. You will do this examination only if you first can demonstrate that much of the efficiency of your program depends on getting this right, however.
Tip: Although you can optimize your sorts with a variety of approaches, you first should be sure that you need an optimization. Then, you should be able to prove that the optimization is in fact making a significant improvement.
An alternative to the selection sort is the insertion sort. The insertion sort generally is a bit quicker than the selection sort and can be represented by the way most people add cards to their poker hands. Each element is picked up in turn and inserted into its place in the array.
Suppose that you start with the children's blocks shown in figure 4.4.
Figure 4.4. Blocks to sort.
The insertion sort examines each value and pushes each into order. First, r is moved before x. Next, a is moved before r. Then, c is moved in after a but before r, and so on. Listing 4.3 illustrates this idea.
Listing 4.3 Using an Insertion Sort
1: // Listing 4.3 - Using an Insertion Sort
2:
3: #include <iostream.h>
4: #include <string.h>
5: void InsertionSort(char *Array);
6:
7: // Ask for a buffer full of characters
8: // Use the insertion sort to sort 'em
9: int main()
10: {
11: char buffer[100];
12:
13: cout << "Enter up to 100 characters: ";
14: cin.getline(buffer,100);
15:
16: cout << "Unsorted:\t" << buffer << endl;
17:
18: InsertionSort(buffer);
19:
20: cout << "Sorted:\t\t" << buffer << endl;
21:
22: return 0;
23: }
24:
25: enum BOOL {FALSE, TRUE};
26: // Examine each member in turn, inserting into place
27: // any smaller member
28: void InsertionSort(char *Input)
29: {
30: const int iLen = strlen(Input)+1; // length of input string
31: char *Array = new char[iLen]; // array on which we'll work
32: Array[0]=-1; // force sentinel
33: for (int i = 0; i<iLen; i++) // fill in from input buffer
34: Array[i+1]=Input[i];
35: Array[iLen]='\0'; // null terminate our working array
36: int ArrayLen = strlen(Array); // ArrayLen = N (number to sort)
37:
38: for (int ctr = 2; ctr < ArrayLen; ctr++)
39: {
40: int val = Array[ctr];
41:
42: for (int ctrTwo = ctr; Array[ctrTwo-1] > val; ctrTwo--)
43: Array[ctrTwo]=Array[ctrTwo-1];
44:
45: Array[ctrTwo]=val;
46: }
47:
48: for (i = 0; i<strlen(Input); i++) // ready the return buffer
49: Input[i]=Array[i+1];
50: }
Output:
Enter up to 100 characters: xracdbsb
Unsorted: xracdbsb
Sorted: abbcdrsx
Enter up to 100 characters: jkdfsla;jfaisuvioaie;jiqopu7vzm,zC>320akweuioa
Unsorted: jkdfsla;jfaisuvioaie;jiqopu7vzm,zC>320akweuioa
Sorted: ,0237;;>Caaaaadeeffiiiiijjjkklmooopqssuuuvvwzz
d:\bc4\book2\exe>proj0000
Enter up to 100 characters: Eternal vigilance is the price of liberty
Unsorted: Eternal vigilance is the price of liberty
Sorted: Eaabcceeeeefghiiiiilllnnoprrrstttvy
Analysis:
Once again, the user is prompted to enter a string in line 13, and the string is passed to InsertionSort() in line 18.
The very first thing InsertionSort() does, in lines 30 through 36, is to create a copy of the array, inserting the value -1 as the very first value (Array[0]). If the original buffer was x, r, a, c, d, b, s, b, the array now is -1, x, r, a, c, d, b, s, b.
In line 38, a counter (ctr) is created and a for loop ticks through every element in the array beginning at offset 2 (in this case, the value r). The local variable var is set to point to that value; and another counter, ctrTwo, is set to the value of ctr). For each element to the left of the value at ctr (in this case, x and -1), a comparison is made. If the value to the left is greater than the target value, a swap is performed. In this case, x is moved to the position formerly held by r. Finally, when r's place is found, it is swapped in, leaving the array -1, r, x, a, c, d, b, s, b.
This process is repeated for each member in the array, so after the next round, a has been moved into place, leaving -1, a, r, x, c, d, b, s, b.
When the array is sorted fully, the new array (without the sentinel) is copied back into the buffer, returned to the calling function, and printed.
The bubble sort is popular because it is easy to implement, easy to understand, and has the desirable trait of quickly moving the smallest element to the top of the list. The bubble sort also is quite efficient with data that already is nearly sorted; it wastes little time on resorting already sorted data.
The name bubble sort comes from the fact that smaller values bubble up through the array to the top, much like gas bubbles in a glass of soda (you may know this as pop, fizz, or some other bizarre regional variant). Listing 4.4 illustrates a simple bubble sort.
Listing 4.4 Using a Bubble Sort
1: // Listing 4.4 - Using a Bubble Sort
2:
3: #include <iostream.h>
4: #include <string.h>
5: void BubbleSort(char *Array);
6: void swap(char& i, char& j);
7:
8: // Ask for a buffer full of characters
9: // Use the bubble sort to sort 'em
10: int main()
11: {
12: char buffer[100];
13:
14: cout << "Enter up to 100 characters: ";
15: cin.getline(buffer,100);
16:
17: cout << "Unsorted:\t" << buffer << endl;
18:
19: BubbleSort(buffer);
20:
21: cout << "Sorted:\t\t" << buffer << endl;
22:
23: return 0;
24: }
25:
26: enum BOOL {FALSE, TRUE};
27: // Examine each member in turn, bubbling into place
28: // any smaller member
29: void BubbleSort(char *Input)
30: {
31: int N = strlen(Input);
32: for (int i = 0; i< N; i++)
33: for (int j = N-1; j>0; j--)
34: if (Input[j-1] > Input[j])
35: swap(Input[j-1],Input[j]);
36: }
37:
38: void swap(char& i, char& j)
39: {
40: char temp;
41: temp = j;
42: j = i;
43: i = temp;
44: }
Output:
Enter up to 100 characters: 54321
Unsorted: 54321
Sorted: 12345
Analysis:
The body of the program, in lines 8 through 24, is essentially identical to the previous programs, except that BubbleSort() is called.
The sort itself is fairly simple. Each member of the array is visited left to right in the outer loop in line 32. For each of these members, the inner loop is visited right to left in lines 33 through 35. Smaller values are bubbled up. This process can be seen most clearly by adding a print statement, as shown in listing 4.5.
Listing 4.5 Using a Bubble Sort with a Print Listing
1: // Listing 4.5 - Using a Bubble Sort with a Print Listing
2:
3: #include <iostream.h>
4: #include <string.h>
5: void BubbleSort(char *Array);
6: void swap(char& i, char& j);
7:
8: // Ask for a buffer full of characters
9: // Use the bubble sort to sort 'em
10: int main()
11: {
12: char buffer[100];
13:
14: cout << "Enter up to 100 characters: ";
15: cin.getline(buffer,100);
16:
17: cout << "Unsorted:\t" << buffer << endl;
18:
19: BubbleSort(buffer);
20:
21: cout << "Sorted:\t\t" << buffer << endl;
22:
23: return 0;
24: }
25:
26: enum BOOL {FALSE, TRUE};
27: // Examine each member in turn, bubbling into place
28: // any smaller member
29: void BubbleSort(char *Input)
30: {
31: int N = strlen(Input);
32: for (int i = 0; i< N; i++)
33: {
34: cout << "i: " << i << " buffer: " << Input << endl;
35: for (int j = N-1; j>0; j--)
36: if (Input[j-1] > Input[j])
37: swap(Input[j-1],Input[j]);
38: }
39: }
40:
41: void swap(char& i, char& j)
42: {
43: char temp;
44: temp = j;
45: j = i;
46: i = temp;
Note: Line numbers have been added to the input to make analysis easier. Your output will not have these line numbers.
Output:
1: Enter up to 100 characters: 54321
2: Unsorted: 54321
3: i: 0 buffer: 54321
4: i: 1 buffer: 15432
5: i: 2 buffer: 12543
6: i: 3 buffer: 12354
7: i: 4 buffer: 12345
8: Sorted: 12345
Analysis:
Listing 4.5 is just like listing 4.4, except that in line 34 the value of i is printed each time it changes. The output has been numbered to make analysis easier, although your actual output will not be numbered.
Line 3 of the output shows the buffer before the inner loop runs, and the numbers are in the sequence as entered: 5,4,3,2,1. After the first complete run of the inner loop, the variable i is incremented to 1; and the lowest value in the buffer, 1, has bubbled up to the top, as shown in line 4. After another run of the inner buffer, i is incremented to 2; and the second lowest value, 2, has bubbled up to the second position. This process continues until the entire array has been walked through in the outer loop, by which time the array is in order.
Tip: Although the bubble sort often is derided for being slow and inefficient, if you need to get the first results of a sort quickly, the bubble sort often can be the best option.
The bubble sort can be very convenient when you need to move values quickly to the top of the array. In fact, with a minor change, the flow can be reversed. Listing 4.6 shows the effect of bubbling downward, moving the highest values into the end of the array.
Listing 4.6 Bubbling Downward
1: // Listing 4.6 - Bubbling Downward
2:
3: #include <iostream.h>
4: #include <string.h>
5: void BubbleSort(char *Array);
6: void swap(char& i, char& j);
7:
8: // Ask for a buffer full of characters
9: // Use the insertion sort to sort 'em
10: int main()
11: {
12: char buffer[100];
13:
14: cout << "Enter up to 100 characters: ";
15: cin.getline(buffer,100);
16:
17: cout << "Unsorted:\t" << buffer << endl;
18:
19: BubbleSort(buffer);
20:
21: cout << "Sorted:\t\t" << buffer << endl;
22:
23: return 0;
24: }
25:
26: enum BOOL {FALSE, TRUE};
27: // Examine each member in turn, bubbling highest values
28: // down into place
29: void BubbleSort(char *Input)
30: {
31: int N = strlen(Input);
32: for (int i = N; i>=1; i--)
33: {
34: cout << "i: " << i << " buffer: " << Input << endl;
35: for (int j = 1; j<i; j++)
36: if (Input[j-1] > Input[j])
37: swap(Input[j-1],Input[j]);
38: }
39: }
40:
41: void swap(char& i, char& j)
42: {
43: char temp;
44: temp = j;
45: j = i;
46: i = temp;
47: }
Note: Line numbers have been added to the input to make analysis easier. Your output will not have these line numbers.
Output:
1: Enter up to 100 characters: 54321
2: Unsorted: 54321
3: i: 5 buffer: 54321
4: i: 4 buffer: 43215
5: i: 3 buffer: 32145
6: i: 2 buffer: 21345
7: i: 1 buffer: 12345
8: Sorted: 12345
Analysis:
Listing 4.6 differs from listing 4.5 only in the logic of the bubble sort itself. Line 32 of listing 4.5 shows the outer loop counting upward from 0for (int i = 0; i< N; i++) whereas listing 4.6 sets i to the value of N and then counts down while i is greater than or equal to 1. Listing 4.5 counts from left to right, and listing 4.6 counts from right to left.
Listing 4.5's inner loop starts at the far right and moves left; listing 4.6's inner loop starts at the far left and moves right. The net effect of this is that the higher values are bubbled downward.
In line 3 of the output, i has been initialized to 5 (the value of N), and the array is fully unsorted. In line 4 of the output, i has been decremented and the value 5 has fallen to the bottom of the array. In line 4, i again has been decremented, and now the second highest value, 4, has fallen to the next-to-last position. In this way, the array is sorted in low-to-high order by pushing down the values in the order high to low.
Bubble sorts can be very convenient, even though they are somewhat less efficient than other sorts. If you were to take a directory listing and sort it using the bubble sort, each entry could be shown as it is made available (at each iteration of the outer loop). Although the overall sort might be marginally slower, preliminary results could be provided earlier than with some other sorts.
You might make two observations about the bubble sort. The first is that if you are sorting upward, after you move a value into position, there is no reason to compare other values with that value ever again. That is, if you bubble the lowest number to the top of the array, there is no reason to compare other numbers to see whether they are lower than that number. After all, that is what a bubble sort does, it moves the lowest number up into position, and then it moves the second lowest, and so on.
The second observation is that if you make no swaps in any comparison all the way through one iteration, you are done; no future iterations will create swaps either. Listing 4.7 illustrates these improvements.
Listing 4.7 Improving the Bubble Sort
1: // listing 4.7 - Improving the Bubble Sort
2:
3: #include <iostream.h>
4: #include <string.h>
5: void BubbleSort(char *);
6: void BetterBubble(char *);
7: void swap(char& i, char& j);
8:
9: // Ask for a buffer full of characters
10: // Use the bubble sort to sort 'em
11: int main()
12: {
13: char buffer[100];
14: char buff2[100];
15:
16: cout << "Enter up to 100 characters: ";
17: cin.getline(buffer,100);
18: strcpy(buff2,buffer);
19:
20: cout << "Unsorted:\t" << buffer << endl;
21:
22: BubbleSort(buffer);
23:
24: cout << "Sorted:\t\t" << buffer << endl;
25:
26: cout << "press Enter to continue";
27: cin.getline(buffer,10);
28:
29: BetterBubble(buff2);
30:
31: cout << "Sorted:\t\t" << buff2 << endl;
32:
33: return 0;
34: }
35:
36: enum BOOL {FALSE, TRUE};
37: // Examine each member in turn, bubbling into place
38: // any smaller member
39: void BubbleSort(char *Input)
40: {
41: int N = strlen(Input);
42: int compare = 0;
43: int didSwap = 0;
44: for (int i = 0; i< N; i++)
45: {
46: for (int j = N-1; j>0; j--)
47: {
48: compare++;
49: if (Input[j-1] > Input[j])
50: {
51: didSwap++;
52: swap(Input[j-1],Input[j]);
53: }
54: }
55: }
56: cout << compare << " compares; " << didSwap << " swaps" << endl;
57: }
58:
59: void BetterBubble(char *Input)
60: {
61: int n = strlen(Input);
62: int compare = 0;
63: int didSwap = 0;
64: BOOL swapped = TRUE;
65:
66: for (int i=0; swapped; i++)
67: {
68: swapped = FALSE;
69: for (int j=n-1;j>i; j--)
70: {
71: compare++;
72: if (Input[j-1] > Input[j])
73: {
74: swap(Input[j-1], Input[j]);
75: swapped = TRUE;
76: didSwap++;
77: }
78: }
79: }
80: cout << compare << " compares; " << didSwap << " swaps" << endl;
81: }
82:
83: void swap(char& i, char& j)
84: {
85: char temp;
86: temp = j;
87: j = i;
88: i = temp;
89: }
Output:
Enter up to 100 characters: asdfghjklzxcvbnmpoiuytrewq
Unsorted: asdfghjklzxcvbnmpoiuytrewq
650 compares; 108 swaps
Sorted: abcdefghijklmnopqrstuvwxyz
press Enter to continue
297 compares; 108 swaps
Sorted: abcdefghijklmnopqrstuvwxyz
d:\bc4\book2\exe>proj0001
Enter up to 100 characters: abcdefghijklmnopqrstuvwxyz
Unsorted: abcdefghijklmnopqrstuvwxyz
650 compares; 0 swaps
Sorted: abcdefghijklmnopqrstuvwxyz
press Enter to continue
25 compares; 0 swaps
Sorted: abcdefghijklmnopqrstuvwxyz
Analysis:
Listing 4.7 runs two versions of the BubbleSort(). The first version is just like listing 4.4, except that it keeps track of comparison in line 48; if there is a swap, it counts that as well in line 51. After the array is sorted, it prints these counts as a metric of how hard the sort worked.
The second version of BubbleSort() implements the two optimizations described in the preceding paragraph. The outer for loop in line 66 ends if nothing was swapped. The inner for loop is modified to check whether j is greater than i rather than 0; that is, it doesn't check those items already sorted. The count of comparisons and swaps is printed in line 80.
As you can see from the output, a nearly random array of characters falls from 650 compares and 108 swaps to 297 compares and 108 swaps. A sorted array falls from 650 compares and no swaps to 25 compares and no swaps. This optimization, therefore, is very much worth the tiny extra effort.
Tip: The correct optimization can save you significant processing time. The trick is to make sure that you are fixing a real problem. The fix must not make other conditions worse, and the problem you are solving must matter in your program. There is no sense in fixing a part of the code that you almost never call and that doesn't take very long in the first place.
The most popular sort among computer programmers may well be QuickSort(). This approach, invented in 1960 by C.A.R. Hoare, is probably not the quickest sort (despite its name) available, but it is easy to implement, it works well for many needs, and it has been adopted by many compiler vendors. The standard C library calls for a Qsort, which does not guarantee that the QuickSort() will be used, but many programmers assume that QuickSort() is the implementation nonetheless.
To see how QuickSort() works, assume that you have the array shown in figure 4.5.
Figure 4.5. An initial array.
The first time you call QuickSort(), you pass in the array and ask it to sort starting at position 0, which is given the name left. You also ask it to sort the entire array by telling it the size of the array, in this case 8, called right.
On each call to QuickSort(), the right parameter (8) is compared with the left parameter (0). If right is not greater than left, the function exits.
The value of the entry in the rightmost position (Array[right-1]) is saved as target. (In this case, target holds the value f.) Two local variables (i and j) are initialized. i is initialized to point to the extreme left (b), and j is initialized to point to the rightmost value other than the target (in this case, e).
An inner loop is created in which i will be incremented and j will be decremented. When the letters cross over, the inner loop will end.
Each time through the inner loop, i is incremented until it points to a value that is greater than or equal to the target. In this case, it will end up pointing to r and have the value 1 (remembering that arrays count from 0).
j is decremented each time through the inner loop, and moves left until it finds a value that is less than or equal to the target. Because in this case j was initialized to position 6 and holds the value e, it will not move at all.
If the letters have not crossed over, the values they point to are swapped. The result of this is shown in figure 4.6.
Figure 4.6. After the first swap.
The second time through the inner loop, i starts out with the value 1 and continues looking for a value greater than or equal to the target, thus moving right to position 3. j starts out with the value 6, pointing to r, and moves left until it finds a value less than or equal to the target. It stops at position 4 and i stops at position 3, and these are swapped. The result is shown in figure 4.7.
Figure 4.7. After the second swap.
The variables i and j look again, but this time when they stop, i is pointing to position 4 and j is pointing to position 3, and they have crossed over one another. This terminates the inner loop, without an additional swap.
The outer loop now swaps the value at i with the target. The result is shown in figure 4.8.
Figure 4.8.After the outer loop swap.
Note that at this point the target, F, is at position 4. Everything to the left of the target now is smaller than it, and everything to its right now is larger. The array has been broken into two parts around the target.
At this point, QuickSort() is called again, twice. The first call sets left to 0 and right to the value of i (4), and the second call sets left to the value of i+1 (5) and right to the value of right (8). This is illustrated in figure 4.9.
Figure 4.9.Ready for the next QuickSort().
Each of these arrays then will be sorted recursively, as shown in listing 4.8.
Listing 4.8 Using QuickSort()
1: // Listing 4.8 - Using QuickSort()
2:
3: #include <iostream.h>
4: #include <string.h>
5: void QuickSort(char*, int, int);
6: void swap(char& i, char& j);
7:
8: // Ask for a buffer full of characters
9: // Use Quicksort to sort 'em
10: int main()
11: {
12: char buffer[100];
13:
14: cout << "Enter up to 100 characters: ";
15: cin.getline(buffer,100);
16:
17: cout << "Unsorted:\t" << buffer << endl;
18:
19: int len = strlen(buffer);
20: QuickSort(buffer,0,len);
21:
22: cout << "Sorted:\t\t" << buffer << endl;
23:
24: return 0;
25: }
26:
27: enum BOOL {FALSE, TRUE};
28: // Sort each part, then recursively call
29: // the Quicksort procedure
30: void QuickSort(char *Input, int left, int right)
31: {
32: if (right > left)
33: {
34: char target = Input[right-1];
35: int i = left-1;
36: int x = right-1;
37: for (;;)
38: {
39: while (Input[++i] < target)
40: ;
41: while (Input[--x] > target)
42: ;
43: if (i >= x)
44: break;
45: swap(Input[i], Input[x]);
46: }
47: swap(Input[i], Input[right-1]);
48: QuickSort(Input,left,i);
49: QuickSort(Input,i+1,right);
50: }
51: }
52:
53: void swap(char& i, char& j)
54: {
55: char temp;
56: temp = j;
57: j = i;
58: i = temp;
59: }
Output:
Enter up to 100 characters: jaskl;jfdk;a3uioapvjiasd
Unsorted: jaskl;jfdk;a3uioapvjiasd
Sorted: 3;;aaaaddfiijjjkklopssuv
Enter up to 100 characters: Eternal vigalence is the price of liberty
Unsorted: Eternal vigalence is the price of liberty
Sorted: Eaabcceeeeeefghiiiilllnnoprrrstttvy
Analysis:
Once again, the body of the main program differs from the previous programs only in that QuickSort() is called. Initially, Quicksort() is called with O and N--that is the entire array is to be sorted.
In line 32, the end condition for the recursion is tested, the second parameter must be greater than the first, or you have "crossed over" and it is time to return. In line 34, the last letter in the array is set as the target. In lines 35 and 36, two local variables are initialized to the leftmost and rightmost entries in the array not counting the target.
The leftmost pointer (Input[i]) is incremented to point to the first letter that is not less in value than the target, and the rightmost pointer (Input[x]) is decremented until it points to a letter that is not greater than the target. If the letters have crossed over, the loop is exited as shown in lines 43 and 44. Otherwise, not having crossed over, the letters now are swapped.
In either case, the value at the left pointer then is swapped with the target. The array then is divided (unevenly) into everything up to where i now is pointing and everything after that point, and QuickSort() then is called recursively on the remaining arrays.
Note: QuickSort() is a very popular sort, but it is important to note that the QSORT provided by ANSI standard libraries is not guaranteed to use QuickSort().
Until now, you have been sorting letters in an array. It is possible, however, that your objects to be sorted are substantially larger than letters. You might, for example, have a collection of strings to sort.
Each string might be hundreds of bytes large, and exchanging two strings might entail significant overhead. Because each of these sorting algorithms involves multiple swaps, it would be best if it were possible to avoid more than N swaps. In other words, you will want to swap each string no more than once.
To accomplish this, you create an array of pointers to your objects, and then swap the pointers. After the array of pointers is fully sorted, you then can rearrange your array of objects into the sorted order. Listing 4.9 illustrates this technique by using QuickSort() on an array of string objects.
Listing 4.9 Sorting Pointers
1: // Listing 4.9 - Sorting Pointers
2:
3: #include <iostream.h>
4: #include <string.h>
5: #include "string.hpp"
6:
7: void QuickSort(String**, int, int);
8: void swap(String*& i, String*& j);
9:
10: // Ask for a buffer full of characters
11: // Use the insertion sort to sort 'em
12: int main()
13: {
14: char buffer[100];
15: String *pArray[5];
16: for (int i = 0; i<5; i++)
17: {
18: cout << "Enter the string: ";
19: cin.getline(buffer,100);
20: pArray[i] = new String(buffer);
21: }
22:
23: cout << "\nUnsorted: "<< endl;
24: for (i = 0; i < 4; i++)
25: cout << *pArray[i] << ", ";
26: cout << *pArray[4] << endl;
27:
28: QuickSort(pArray,0,5);
29:
30: cout << "\nSorted: "<< endl;
31: for (i = 0; i < 4; i++)
32: cout << *pArray[i] << ", ";
33: cout << *pArray[4] << endl;
34:
35: return 0;
36: }
37:
38: // QuickSort method modified to take pointers.
39: // Examine each member in turn, inserting into place
40: // any smaller member
41: void QuickSort(String** Input, int left, int right)
42: {
43: if (right > left)
44: {
45: String* target = Input[right-1];
46: int i = left-1;
47: int x = right-1;
48: for (;;)
49: {
50: while (*Input[++i] < *target)
51: ;
52: while (*Input[--x] > *target)
53: ;
54:
55: if (i >= x)
56: break;
57: swap(Input[i], Input[x]);
58: }
59: swap(Input[i], Input[right-1]);
60: QuickSort(Input,left,i);
61: QuickSort(Input,i+1,right);
62: }
63: }
64:
65: // note reference to pointers!
66: void swap(String*& i, String*& j)
67: {
68: String* temp;
69: temp = j;
70: j = i;
71: i = temp;
72: }
Output:
Enter the string: eternal
Enter the string: vigalence
Enter the string: is the
Enter the string: price of
Enter the string: liberty
Unsorted:
eternal, vigalence, is the, price of, liberty
Sorted:
eternal, is the, liberty, price of, vigalence
Analysis:
Listing 4.8 is similar to listing 4.7, except that in this case, pointers to the strings are sorted, rather than the strings themselves.
This requires a change to the signatures of both QuickSort() and Swap(). QuickSort() now receives an array of pointers to strings, which can be represented as String*[], or equally well as String**.
What is passed to Swap() now will be a pointer to a String, which is itself passed by reference, so the signature is a reference to pointer and thus Swap(String*& i, String*& j).
The array of pointers to strings is initialized in lines 16 through 21. The user repeatedly is prompted to enter a string, which is placed in a C-style string buffer. This then is used as a parameter to the constructor of a String object created on the heap, and the unnamed pointer returned by the operator new is stored in pArray.
The unsorted contents of this array are printed in lines 23 through 26, and then the array is passed to QuickSort() in line 28. The returned values, now sorted, are printed in lines 30 through 33.
Careful examination of lines 57 and 59 of QuickSort() reveal that only the pointers are swapped within the array, rather than the strings themselves. Note, however, that the comparisons in lines 50 and 52 involve the strings and not the pointers. The idea is to sort by the value of the strings, but to swap only the pointers.
As discussed, Swap() takes as its parameters references to the two String pointers to swap. It could well have taken pointers to these pointers, but then all the pointers would have had to be dereferenced. This way, the clean interface is preserved. Note, in line 68, that temp must be declared as a pointer to String because, of course, that is what it must hold.
Now that QuickSort() is working well for you, you will want to parameterize it to take pointers to any objects. This process is fairly straightforward; simply create a template form of both QuickSort() and Swap().
In the body of each of these functions, you must replace the specific type (String*) with a parameterized type (T*). You do not need to instantiate a particular instance of the template (you don't write QuickSort<String*>), because function overloading will take care of that for you. Listing 4.10 illustrates parameterizing the QuickSort() function and then using it with an array of String pointers and an array of int pointers.
Listing 4.10 Using a Parameterized QuickSort
1: // Listing 4.10 - Using a Parameterized QuickSort
2:
3: #include <iostream.h>
4: #include <string.h>
5: #include <stdlib.h>
6:
7: #include "string.hpp"
8:
9: template <class T> void QuickSort(T*, int, int);
10: template <class T> void Swap(T& i, T& j);
11:
12: // Ask for a buffer full of characters
13: // Use the insertion sort to sort 'em
14: int main()
15: {
16: char buffer[100];
17: String *pArray[5];
18: for (int i = 0; i<5; i++)
19: {
20: cout << "Enter the string: ";
21: cin.getline(buffer,100);
22: pArray[i] = new String(buffer);
23: }
24:
25: cout << "\nUnsorted: "<< endl;
26: for (i = 0; i < 4; i++)
27: cout << *pArray[i] << ", ";
28: cout << *pArray[4] << endl;
29:
30: QuickSort(pArray,0,5);
31:
32: cout << "\nSorted: "<< endl;
33: for (i = 0; i < 4; i++)
34: cout << *pArray[i] << ", ";
35: cout << *pArray[4] << endl;
36:
37: int *intArray[10];
38: for (i = 0; i < 10; i++)
39: {
40: intArray[i] = new int;
41: *intArray[i] = rand();
42: }
43:
44: cout << "\nUnsorted: "<< endl;
45: for (i = 0; i < 9; i++)
46: cout << *intArray[i] << ", ";
47: cout << *intArray[9] << endl;
48:
49: QuickSort(intArray,0,10);
50:
51: cout << "\nSorted: "<< endl;
52: for (i = 0; i < 9; i++)
53: cout << *intArray[i] << ", ";
54: cout << *intArray[9] << endl;
55:
56: return 0;
57: }
58:
59: // Templatized Quicksort Function
60: template <class T>
61: void QuickSort(T* Input, int left, int right)
62: {
63: if (right > left)
64: {
65: T target = Input[right-1];
66: int i = left-1;
67: int x = right-1;
68: for (;;)
69: {
70: while (*Input[++i] < *target)
71: ;
72: while (*Input[--x] > *target)
73: ;
74:
75: if (i >= x)
76: break;
77: Swap(Input[i], Input[x]);
78: }
79:
80: Swap(Input[i], Input[right-1]);
81: QuickSort(Input,left,i);
82: QuickSort(Input,i+1,right);
83:
84: }
85: }
86:
87: template <class T>
88: inline void Swap(T& i, T& j)
89: {
90: T temp;
91: temp = j;
92: j = i;
93: i = temp;
94: }
Output:
Enter the string: eternal
Enter the string: vigalence
Enter the string: is the
Enter the string: price of
Enter the string: liberty
Unsorted:
eternal, vigalence, is the, price of, liberty
Sorted:
eternal, is the, liberty, price of, vigalence
Unsorted:
346, 130, 10982, 1090, 11656, 7117, 17595, 6415, 22948, 31126
Sorted:
130, 346, 1090, 6415, 7117, 10982, 11656, 17595, 22948, 31126
Analysis:
Listing 4.10 is similar to listing 4.9, except that the type of the object to be sorted has been parameterized in the declarations of both QuickSort() in line 9 and Swap() in line 10.
Invocation of QuickSort() on objects of type String is shown in line 30, and invocation of QuickSort() on integers is shown in line 49. Note, again, that no special declaration of these instances is required; function overloading does the job of telling the compiler to create an instance of these functions based on the template.
The integers for the unsorted array are created in line 41 by invocation of the standard library rand() function. This is not a great way to generate true random numbers, but it suffices for the purpose of demonstrating the sort.
QuickSort() is a good general-purpose sort, but its efficiency depends very much on what object you use as the target. In the versions shown earlier, the final member of the array always was chosen as the target. This method can introduce inefficiencies if the last member of the target happens to be the largest (or smallest) member of the array.
Many programmers work around this problem by using the Median of Three rule. To use this rule, choose the first, last, and middle elements in the array. Sort them and choose the middle value. Use that value as the target. Listing 4.11 illustrates QuickSort() using the Median of Three rule.
Listing 4.11 Using QuickSort() with Median of Three
1: // Listing 4.11 Using QuickSort() with Median of Three
2:
3: #include <iostream.h>
4: #include <string.h>
5: #include "string.hpp"
6:
7: // function prototypes
8: void QuickSort(String**, int, int);
9: void Swap(String*& i, String*& j);
10: int Median(String**,int,int,int);
11:
12: int main()
13: {
14: // prompt for five strings
15: // sort them using QuickSort and Median of Three
16: char buffer[100];
17: String *pArray[5];
18: for (int i = 0; i<5; i++)
19: {
20: cout << "Enter the string: ";
21: cin.getline(buffer,100);
22: pArray[i] = new String(buffer);
23: }
24:
25: cout << "\nUnsorted: "<< endl;
26: for (i = 0; i < 4; i++)
27: cout << *pArray[i] << ", ";
28: cout << *pArray[4] << endl;
29:
30: QuickSort(pArray,0,5);
31:
32: cout << "\nSorted: "<< endl;
33: for (i = 0; i < 4; i++)
34: cout << *pArray[i] << ", ";
35: cout << *pArray[4] << endl;
36:
37: return 0;
38: }
39:
40: // given three positions, return the middle value
41: int Median(String** array,int left,int right,int middle)
42: {
43: if (array[left] < array[right])
44: return array[left] > array[middle] ? left : middle;
45: else
46: return array[right] < array[middle] ? middle : right;
47: }
48:
49: // QuickSort implemented with Median of Three
50: void QuickSort(String** Input, int left, int right)
51: {
52: if (right > left)
53: {
54: int med = Median(Input,left,right-1, (left + right) /2);
55: String* target = Input[med];
56: int i = left-1;
57: int x = right;
58: for (;;)
59: {
60: while (*Input[++i] < *target)
61: ;
62: while (*Input[--x] > *target)
63: ;
64:
65: if (i >= x)
66: break;
67: Swap(Input[i], Input[x]);
68: }
69: Swap(Input[i], Input[med]);
70: QuickSort(Input,left,i);
71: QuickSort(Input,i+1,right);
72: }
73: }
74:
75: void Swap(String*& i, String*& j)
76: {
77: String* temp;
78: temp = j;
79: j = i;
80: i = temp;
81: }
Output:
Enter the string: eternal
Enter the string: vigalence
Enter the string: is the
Enter the string: price of
Enter the string: liberty
Unsorted:
eternal, vigalence, is the, price of, liberty
Sorted:
eternal, is the, liberty, price of, vigalence
Unsorted:
346, 130, 10982, 1090, 11656, 7117, 17595, 6415, 22948, 31126
Sorted:
130, 346, 1090, 6415, 7117, 10982, 11656, 17595, 22948, 31126
Analysis:
Listing 4.11 is exactly like listing 4.9, except in how the target value is chosen. In the previous examples, the target value was always the last value in the array. This method works well for an unsorted list, but does not work well for a list that is fully or nearly fully sorted.
In line 54, the target position is chosen by calling Median() and passing in the leftmost value, the rightmost value, and a value from the middle of the array. Median() returns the position of the middle of these three values, and that position is used as the target or pivot point for the current round of the QuickSort(). With a sorted or nearly sorted array, this dramatically reduces the number of compares and swaps required.
Today you learned a number of techniques for sorting. Although academic books on sorts spend a great deal of time on the mathematics of sorts, proving why this one or that one is optimal in a particular situation, real-world programmers generally stick with a few tried-and-true sort algorithms.
You saw how insertion and selection sorts work, how the bubble sort works, and what it can do for your program. Then you saw how to use QuickSort(). You learned how to sort pointers when sorting large objects, and how to make a template of your sort algorithm so that you can sort differing types of objects. Finally, you learned how to set the target value for QuickSort() using the Median of Three rule.
Q: What are the important things to look for when evaluating the performance of a sorting algorithm?
A: The most important issue is the number of times it must do its basic comparison, as a function of the number of items being sorted. Usually this is proportional to n squared (the number of items, squared), but some, like QuickSort(), are better. This should be evaluated for the common case, and for some special cases.
Q: What are the special cases?
A: The special cases are when the data already is sorted, both in the order you want and in the opposite order. Because data often will arrive in these orders, a good sorting algorithm will have good behavior on these cases.
Q: How do the sorts in this chapter stack up, according to these criteria?
A: SelectionSort() is pretty bad, doing n squared operations in all cases. (For every slot in the final, sorted list, it checks every one of the remaining values in order to find the lowest. Although this is not exactly n squared, it is proportional to it, which is what matters.)
InsertionSort() still is considered to be an n-squared algorithm, even though it short-circuits many of the operations when items are found to be sorted already. Given a completely sorted list, InsertionSort() performance is proportional to n, which is the best possible.
BubbleSort() has similar behavior to InsertionSort(). Both BubbleSort() and InsertionSort() have their best performance on an already sorted list, and their worst on a reverse-sorted list.
QuickSort() is the only algorithm seen so far with n log n performance. This means that the number of operations needed is proportional to n times the logarithm of n. For very long lists, this method is significantly better than n squared.
Q: When should you sort pointers to items instead of the items themselves?
A: Whenever swapping the items is noticeably more costly than swapping pointers. If the items are strings, this is clearly the case. If the items are floats, for example, it is close or the same. (Compare sizeof(float) with sizeof(float *) on your system.) If the items are doubles, pointers probably are better, although it's still pretty close.
The Workshop provides quiz questions to help you solidify your understanding of the material covered, and exercises to provide you with experience in using what you have learned. Try to answer the quiz and exercise questions before checking the answers in Appendix A, and make sure that you understand the answers before continuing to the next chapter.
Go to: Table of Contents | Next Page