www.gibmonks.com

Main Page




Previous Page
Next Page

[Page 982 (continued)]

20.3. 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.


[Page 984]

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).


[Page 985]

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.


[Page 988]

[Page 989]
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 <vector>
 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 <iostream>
 4   using std::cout;
 5   using std::endl;
 6 
 7   #include <vector>
 8   using std::vector;
 9 
10   #include <cstdlib> // prototypes for functions srand and rand
11   using std::rand;
12   using std::srand;
13 
14   #include <ctime> // 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 <iostream>
 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.


[Page 991]

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

[Page 992]

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)



[Page 992]

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



Previous Page
Next Page