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

 

 Unsorted vector:
 30 47 22 67 79 18 60 78 26 54

 split: 30 47 22 67 79 18 60 78 26 54
 30 47 22 67 79
 18 60 78 26 54

 split: 30 47 22 67 79
 30 47 22
 67 79

 split: 30 47 22
 30 47
 22

 split: 30 47
 30
 47

 merge: 30
 47
 30 47

 merge: 30 47
 22
 22 30 47

 split: 67 79
 67
 79

 merge: 67
 79
 67 79

 merge: 22 30 47
 67 79
 22 30 47 67 79

 split: 18 60 78 26 54
 18 60 78
 26 54

 split: 18 60 78
 18 60
 78

 split: 18 60
 18
 60

 merge: 18
 60
 18 60

 merge: 18 60
 78
 18 60 78

 split: 26 54
 26
 54

 merge: 26
 54
 26 54

 merge: 18 60 78
 26 54
 18 26 54 60 78

 merge: 22 30 47 67 79
 18 26 54 60 78
 18 22 26 30 47 54 60 67 78 79

 Sorted vector:
 18 22 26 30 47 54 60 67 78 79

 

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.

---

Figure 20.8. Searching and sorting algorithms with Big O values.

---

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)

---

Figure 20.9. Approximate number of comparisons for common Big O notations.

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