7.8. Sorting Arrays with Insertion Sort

Sorting data (i.e., placing the data into some particular order such as ascending or descending) is one of the most important computing applications.

Insertion Sort

The program in Fig. 7.20 sorts the values of the 10-element array data into ascending order. The technique we use is called insertion sort—a simple, but inefficient, sorting algorithm. The first iteration of this algorithm takes the second element and, if it is less than the first element, swaps it with the first element (i.e., the program inserts the second element in front of 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 i^th iteration of this algorithm, the first i elements in the original array will be sorted.

 1   // Fig. 7.20: fig07_20.cpp
 2   // This program sorts an array's values into ascending order.
 3   #include <iostream>
 4   using std::cout;
 5   using std::endl;
 6
 7   #include <iomanip>
 8   using std::setw;
 9
10   int main()
11   {
12      const int arraySize = 10; // size of array a
13      int data[ arraySize ] = { 34, 56, 4, 10, 77, 51, 93, 30, 5, 52 };
14      int insert; // temporary variable to hold element to insert
15
16      cout << "Unsorted array:\n";
17
18      // output original array
19      for ( int i = 0; i < arraySize; i++ )
20         cout << setw( 4 ) << data[ i ];
21
22      // insertion sort                                                     
23      // loop over the elements of the array                                
24      for ( int next = 1; next < arraySize; next++ )                        
25      {                                                                     
26         insert = data[ next ]; // store the value in the current element   
27                                                                            
28         int moveItem = next; // initialize location to place element       
29                                                                            
30         // search for the location in which to put the current element     
31         while ( ( moveItem > 0 ) && ( data[ moveItem - 1 ] > insert ) )    
32         {                                                                  
33            // shift element one slot to the right                          
34            data[ moveItem ] = data[ moveItem - 1 ];                        
35            moveItem--;                                                     
36         } // end while                                                     
37                                                                            
38         data[ moveItem ] = insert; // place inserted element into the array
39      } // end for                                                          
40
41      cout << "\nSorted array:\n";
42
43      // output sorted array
44      for ( int i = 0; i < arraySize; i++ )
45         cout << setw( 4 ) << data[ i ];
46
47      cout << endl;
48      return 0; // indicates successful termination
49   } // end main

					  

Unsorted array:
  34  56   4  10  77  51  93  30   5  52
Sorted array:
   4   5  10  30  34  51  52  56  77  93

Line 13 of Fig. 7.20 declares and initializes array data with the following values:

34  56  4  10  77  51  93  30  5  52

The program first looks at data[ 0 ] and data[ 1 ], whose values are 34 and 56, respectively. These two elements are already in order, so the program continues—if they were out of order, the program would swap them.

In the second iteration, the program looks at the value of data[ 2 ], 4. This value is less than 56, so the program stores 4 in a temporary variable and moves 56 one element to the right. The program then checks and determines that 4 is less than 34, so it moves 34 one element to the right. The program has now reached the beginning of the array, so it places 4 in data[ 0 ]. The array now is

4  34  56  10  77  51  93  30  5  52

In the third iteration, the program stores the value of data[ 3 ], 10, in a temporary variable. Then the program compares 10 to 56 and moves 56 one element to the right because it is larger than 10. The program then compares 10 to 34, moving 34 right one element. When the program compares 10 to 4, it observes that 10 is larger than 4 and places 10 in data[ 1 ]. The array now is

4  10  34  56  77  51  93  30  5  52

Using this algorithm, at the i^th iteration, the first i elements of the original array are sorted. They may not be in their final locations, however, because smaller values may be located later in the array.

The sorting is performed by the for statement in lines 24–39 that loops over the elements of the array. In each iteration, line 26 temporarily stores in variable insert (declared in line 14) the value of the element that will be inserted into the sorted portion of the array. Line 28 declares and initializes the variable moveItem, which keeps track of where to insert the element. Lines 31–36 loop to locate the correct position where the element should be inserted. The loop terminates either when the program reaches the front of the array or when it reaches an element that is less than the value to be inserted. Line 34 moves an element to the right, and line 35 decrements the position at which to insert the next element. After the while loop ends, line 38 inserts the element into place. When the for statement in lines 24–39 terminates, the elements of the array are sorted.

The chief virtue of the insertion sort is that it is easy to program; however, it runs slowly. This becomes apparent when sorting large arrays.