www.gibmonks.com

Main Page




Previous Page
Next Page

[Page 359]

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. 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 phone directories by last name and, within that, by first name to make it easy to find phone numbers. Virtually every organization must sort some data and, in many cases, massive amounts of data. Sorting data is an intriguing problem that has attracted some of the most intense research efforts in the field of computer science. In this chapter, we discuss a simple sorting scheme. In the exercises and Chapter 20, Searching and Sorting, we investigate more complex schemes that yield superior performance, and we introduce Big O (pronounced "Big Oh") notation for characterizing how hard each scheme must work to accomplish its task.

Performance Tip 7.4

Sometimes, simple algorithms perform poorly. Their virtue is that they are easy to write, test and debug. More complex algorithms are sometimes needed to realize optimal performance.


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 sorta 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 ith iteration of this algorithm, the first i elements in the original array will be sorted.


[Page 360]
Figure 7.20. Sorting an array with insertion sort.
(This item is displayed on pages 360 - 361 in the print version)

 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 continuesif they were out of order, the program would swap them.


[Page 361]

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 ith 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 2439 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 3136 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 2439 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. In the exercises, we will investigate some alternate algorithms for sorting an array. We investigate sorting and searching in greater depth in Chapter 20.


Previous Page
Next Page