Sorting Algorithms
Sorting data (i.e., placing the data into some particular order, such as ascending or descending) is one of the most important computing applications. A bank sorts all checks by account number so that it can prepare individual bank statements at the end of each month. Telephone companies sort their lists of accounts by last name and, further, by first name to make it easy to find phone numbers. Virtually every organization must sort some data, and often, massive amounts of it. Sorting data is an intriguing, computer-intensive problem that has attracted intense research efforts.
An important point to understand about sorting is that the end resultthe sorted vectorwill be the same no matter which algorithm you use to sort the vector. The choice of algorithm affects only the runtime and memory use of the program. In previous chapters, we have introduced the selection sort and insertion sortsimple algorithms to implement, but inefficient. The next section examines the efficiency of these two algorithms using Big O notation. The last algorithmmerge sort, which we introduce in this chapteris much faster but is harder to implement.
20.3.1. Efficiency of Selection Sort
Selection sort is an easy-to-implement, but inefficient, sorting algorithm. The first iteration of the algorithm selects the smallest element in the vector and swaps it with the first element. The second iteration selects the second-smallest element (which is the smallest element of the remaining elements) and swaps it with the second element. The algorithm continues until the last iteration selects the second-largest element and swaps it with the second-to-last element, leaving the largest element in the last index. After the ith iteration, the smallest i elements of the vector will be sorted into increasing order in the first i elements of the vector.
The selection sort algorithm iterates n 1 times, each time swapping the smallest remaining element into its sorted position. Locating the smallest remaining element requires n 1 comparisons during the first iteration, n 2 during the second iteration, then n 3, ..., 3, 2, 1. This results in a total of n(n 1)/2 or (n2 n)/2 comparisons. In Big O notation, smaller terms drop out and constants are ignored, leaving a final Big O of O(n2).
20.3.2. Efficiency of Insertion Sort
Insertion sort is another simple, but inefficient, sorting algorithm. The first iteration of this algorithm takes the second element in the vector and, if it is less than the first element, swaps it with the first element. The second iteration looks at the third element and inserts it into the correct position with respect to the first two elements, so all three elements are in order. At the ith iteration of this algorithm, the first i elements in the original vector will be sorted.
Insertion sort iterates n 1 times, inserting an element into the appropriate position in the elements sorted so far. For each iteration, determining where to insert the element can require comparing the element to each of the preceding elements in the vector. In the worst case, this will require n 1 comparisons. Each individual repetition statement runs in O(n) time. For determining Big O notation, nested statements mean that you must multiply the number of comparisons. For each iteration of an outer loop, there will be a certain number of iterations of the inner loop. In this algorithm, for each O(n) iteration of the outer loop, there will be O(n) iterations of the inner loop, resulting in a Big O of O(n* n) or O(n2).
20.3.3. Merge Sort (A Recursive Implementation)
Merge sort is an efficient sorting algorithm, but is conceptually more complex than selection sort and insertion sort. The merge sort algorithm sorts a vector by splitting it into two equal-sized subvectors, sorting each subvector and then merging them into one larger vector. With an odd number of elements, the algorithm creates the two subvectors such that one has one more element than the other.
The implementation of merge sort in this example is recursive. The base case is a vector with one element. A one-element vector is, of course, sorted, so merge sort immediately returns when it is called with a one-element vector. The recursion step splits a vector of two or more elements into two equal-sized subvectors, recursively sorts each subvector, then merges them into one larger, sorted vector. [Again, if there is an odd number of elements, one subvector is one element larger than the other.]
Suppose the algorithm has already merged smaller vectors to create sorted vectors A:
4 10 34 56 77
and B:
5 30 51 52 93
Merge sort combines these two vectors into one larger, sorted vector. The smallest element in A is 4 (located in the zeroth index of A). The smallest element in B is 5 (located in the zeroth index of B). In order to determine the smallest element in the larger vector, the algorithm compares 4 and 5. The value from A is smaller, so 4 becomes the first element in the merged vector. The algorithm continues by comparing 10 (the second element in A) to 5 (the first element in B). The value from B is smaller, so 5 becomes the second element in the larger vector. The algorithm continues by comparing 10 to 30, with 10 becoming the third element in the vector, and so on.
Figure 20.5 defines class MergeSort and lines 3134 of Fig. 20.6 define the sort function. Line 33 calls function sortSubVector with 0 and size - 1 as the arguments. The arguments correspond to the beginning and ending indices of the vector to be sorted, causing sortSubVector to operate on the entire vector. Function sortSubVector is defined in lines 3761. Line 40 tests the base case. If the size of the vector is 1, the vector is already sorted, so the function simply returns immediately. If the size of the vector is greater than 1, the function splits the vector in two, recursively calls function sortSubVector to sort the two subvectors, then merges them. Line 55 recursively calls function sortSubVector on the first half of the vector, and line 56 recursively calls function sortSubVector on the second half of the vector. When these two function calls return, each half of the vector has been sorted. Line 59 calls function merge (lines 64108) on the two halves of the vector to combine the two sorted vectors into one larger sorted vector.
Figure 20.5. MergeSort class definition.
(This item is displayed on page 986 in the print version)
|
1 // Fig 20.5: MergeSort.h 2 // Class that creates a vector filled with random integers. 3 // Provides a function to sort the vector with merge sort. 4 #include 5 using std::vector; 6 7 // MergeSort class definition 8 class MergeSort 9 { 10 public: 11 MergeSort( int ); // constructor initializes vector 12 void sort(); // sort vector using merge sort 13 void displayElements() const; // display vector elements 14 private: 15 int size; // vector size 16 vector< int > data; // vector of ints 17 void sortSubVector( int, int ); // sort subvector 18 void merge( int, int, int, int ); // merge two sorted vectors 19 void displaySubVector( int, int ) const; // display subvector 20 }; // end class SelectionSort |
Figure 20.6. MergeSort class member-function definition.
(This item is displayed on pages 986 - 988 in the print version)
|
1 // Fig 20.6: MergeSort.cpp 2 // Class MergeSort member-function definition. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include 8 using std::vector; 9 10 #include // prototypes for functions srand and rand 11 using std::rand; 12 using std::srand; 13 14 #include // prototype for function time 15 using std::time; 16 17 #include "MergeSort.h" // class MergeSort definition 18 19 // constructor fill vector with random integers 20 MergeSort::MergeSort( int vectorSize ) 21 { 22 size = ( vectorSize > 0 ? vectorSize : 10 ); // validate vectorSize 23 srand( time( 0 ) ); // seed random number generator using current time 24 25 // fill vector with random ints in range 10-99 26 for ( int i = 0; i < size; i++ ) 27 data.push_back( 10 + rand() % 90 ); 28 } // end MergeSort constructor 29 30 // split vector, sort subvectors and merge subvectors into sorted vector 31 void MergeSort::sort() 32 { 33 sortSubVector( 0, size - 1 ); // recursively sort entire vector 34 } // end function sort 35 36 // recursive function to sort subvectors 37 void MergeSort::sortSubVector( int low, int high ) 38 { 39 // test base case; size of vector equals 1 40 if ( ( high - low ) >= 1 ) // if not base case 41 { 42 int middle1 = ( low + high ) / 2; // calculate middle of vector 43 int middle2 = middle1 + 1; // calculate next element over 44 45 // output split step 46 cout << "split: "; 47 displaySubVector( low, high ); 48 cout << endl << " "; 49 displaySubVector( low, middle1 ); 50 cout << endl << " "; 51 displaySubVector( middle2, high ); 52 cout << endl << endl; 53 54 // split vector in half; sort each half (recursive calls) 55 sortSubVector( low, middle1 ); // first half of vector 56 sortSubVector( middle2, high ); // second half of vector 57 58 // merge two sorted vectors after split calls return 59 merge( low, middle1, middle2, high ); 60 } // end if 61 } // end function sortSubVector 62 63 // merge two sorted subvectors into one sorted subvector 64 void MergeSort::merge( int left, int middle1, int middle2, int right ) 65 { 66 int leftIndex = left; // index into left subvector 67 int rightIndex = middle2; // index into right subvector 68 int combinedIndex = left; // index into temporary working vector 69 vector< int > combined( size ); // working vector 70 71 // output two subvectors before merging 72 cout << "merge: "; 73 displaySubVector( left, middle1 ); 74 cout << endl << " "; 75 displaySubVector( middle2, right ); 76 cout << endl; 77 78 // merge vectors until reaching end of either 79 while ( leftIndex <= middle1 && rightIndex <= right ) 80 { 81 // place smaller of two current elements into result 82 // and move to next space in vector 83 if ( data[ leftIndex ] <= data[ rightIndex ] ) 84 combined[ combinedIndex++ ] = data[ leftIndex++ ]; 85 else 86 combined[ combinedIndex++ ] = data[ rightIndex++ ]; 87 } // end while 88 89 if ( leftIndex == middle2 ) // if at end of left vector 90 { 91 while ( rightIndex <= right ) // copy in rest of right vector 92 combined[ combinedIndex++ ] = data[ rightIndex++ ]; 93 } // end if 94 else // at end of right vector 95 { 96 while ( leftIndex <= middle1 ) // copy in rest of left vector 97 combined[ combinedIndex++ ] = data[ leftIndex++ ]; 98 } // end else 99 100 // copy values back into original vector 101 for ( int i = left; i <= right; i++ ) 102 data[ i ] = combined[ i ]; 103 104 // output merged vector 105 cout << " "; 106 displaySubVector( left, right ); 107 cout << endl << endl; 108 } // end function merge 109 110 // display elements in vector 111 void MergeSort::displayElements() const 112 { 113 displaySubVector( 0, size - 1 ); 114 } // end function displayElements 115 116 // display certain values in vector 117 void MergeSort::displaySubVector( int low, int high ) const 118 { 119 // output spaces for alignment 120 for ( int i = 0; i < low; i++ ) 121 cout << " "; 122 123 // output elements left in vector 124 for ( int i = low; i <= high; i++ ) 125 cout << " " << data[ i ]; 126 } // end function displaySubVector |
Lines 7987 in function merge loop until the program reaches the end of either subvector. Line 83 tests which element at the beginning of the vectors is smaller. If the element in the left vector is smaller, line 84 places it in position in the combined vector. If the element in the right vector is smaller, line 86 places it in position in the combined vector. When the while loop has completed (line 87), one entire subvector is placed in the combined vector, but the other subvector still contains data. Line 89 tests whether the left vector has reached the end. If so, lines 9192 fill the combined vector with the elements of the right vector. If the left vector has not reached the end, then the right vector must have reached the end, and lines 9697 fill the combined vector with the elements of the left vector. Finally, lines 101102 copy the combined vector into the original vector. Figure 20.7 creates and uses a MergeSort object. The output from this program displays the splits and merges performed by merge sort, showing the progress of the sort at each step of the algorithm.
Figure 20.7. MergeSort test program.
(This item is displayed on pages 989 - 991 in the print version)
|
1 // Fig 20.7: Fig20_07.cpp 2 // MergeSort test program. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include "MergeSort.h" // class MergeSort definition 8 9 int main() 10 { 11 // create object to perform merge sort 12 MergeSort sortVector( 10 ); 13 14 cout << "Unsorted vector:" << endl; 15 sortVector.displayElements(); // print unsorted vector 16 cout << endl << endl; 17 18 sortVector.sort(); // sort vector 19 20 cout << "Sorted vector:" << endl; 21 sortVector.displayElements(); // print sorted vector 22 cout << endl; 23 return 0; 24 } // end main
|
Efficiency of Merge Sort
Merge sort is a far more efficient algorithm than either insertion sort or selection sort (although that may be difficult to believe when looking at the rather busy Fig. 20.7). Consider the first (nonrecursive) call to function sortSubVector. This results in two recursive calls to function sortSubVector with subvectors each approximately half the size of the original vector, and a single call to function merge. This call to function merge requires, at worst, n 1 comparisons to fill the original vector, which is O(n). (Recall that each element in the vector is chosen by comparing one element from each of the subvectors.) The two calls to function sortSubVector result in four more recursive calls to function sortSubVector, each with a subvector approximately one quarter the size of the original vector, along with two calls to function merge. These two calls to function merge each require, at worst, n/2 1 comparisons, for a total number of comparisons of O(n). This process continues, each call to sortSubVector generating two additional calls to sortSubVector and a call to merge, until the algorithm has split the vector into one-element subvectors. At each level, O(n) comparisons are required to merge the subvectors. Each level splits the size of the vectors in half, so doubling the size of the vector requires one more level. Quadrupling the size of the vector requires two more levels. This pattern is logarithmic and results in log2 n levels. This results in a total efficiency of O(n log n). Figure 20.8 summarizes many of the searching and sorting algorithms covered in this book and lists the Big O for each of them. Figure 20.9 lists the Big O values we have covered in this chapter along with a number of values for n to highlight the differences in the growth rates.
|
Algorithm |
Location |
Big O |
|---|---|---|
|
Searching Algorithms |
||
|
Linear search |
Section 7.7 |
O(n) |
|
Binary search |
Section 20.2.2 |
O(log n) |
|
Recursive linear search |
Exercise 20.8 |
O(n) |
|
Recursive binary search |
Exercise 20.9 |
O(log n) |
|
Sorting Algorithms |
||
|
Insertion sort |
Section 7.8 |
O(n2) |
|
Selection sort |
Section 8.6 |
O(n2) |
|
Merge sort |
Section 20.3.3 |
O(n log n) |
|
Bubble sort |
Exercises 16.3 and 16.4 |
O(n2) |
|
Quick sort |
Exercise 20.10 |
Worst case: O(n2) |
|
Average case: O(n log n) |
||
|
n |
Approximate decimal value |
O(log n) |
O(n) |
O(n log n) |
O(n2) |
|---|---|---|---|---|---|
|
210 |
1000 |
10 |
210 |
10 · 210 |
220 |
|
220 |
1,000,000 |
20 |
220 |
20 · 220 |
240 |
|
230 |
1,000,000,000 |
30 |
230 |
30 · 230 |
260 |