1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 11-3.
6: /** Sorts the items in an array into ascending order.
7: @pre None.
8: @post theArray is sorted into ascending order; n is unchanged.
9: @param theArray The given array.
10: @param n The size of theArray. */
11: template<class ItemType>
12: void insertionSort(ItemType theArray[], int n)
13: {
14: // unsorted = first index of the unsorted region,
15: // loc = index of insertion in the sorted region,
16: // nextItem = next item in the unsorted region.
17: // Initially, sorted region is theArray[0],
18: // unsorted region is theArray[1..n−1].
19: // In general, sorted region is theArray[0..unsorted−1],
20: // unsorted region theArray[unsorted..n−1]
21: for (int unsorted = 1; unsorted < n; unsorted++)
22: {
23: // At this point, theArray[0..unsorted−1] is sorted.
24: // Find the right position (loc) in theArray[0..unsorted]
25: // for theArray[unsorted], which is the first entry in the
26: // unsorted region; shift, if necessary, to make room
27: ItemType nextItem = theArray[unsorted];
28: int loc = unsorted;
29: while ((loc > 0) && (theArray[loc − 1] > nextItem))
30: {
31: // Shift theArray[loc − 1] to the right
32: theArray[loc] = theArray[loc − 1];
33: loc– –;
34: } // end while
35: // At this point, theArray[loc] is where nextItem belongs
36:
37: theArray[loc] = nextItem; // Insert nextItem into sorted region
38: } // end for
39: } // end insertionSort