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.
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 4 using std::cout; 5 using std::endl; 6 7 #include 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: "; 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 << " Sorted array: "; 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
|
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.
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.