1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: // Listing 11-3.
6: #include <iostream>
7: #include <string>
9: using namespace std;
10: template<class ItemType>
12: /** Sorts the items in an array into ascending order.
13: @pre None.
14: @post theArray is sorted into ascending order; n is unchanged.
15: @param theArray The given array.
16: @param n The size of theArray. */
17: void insertionSort(ItemType theArray[], int n)
18: {
19: // unsorted = first index of the unsorted region,
20: // loc = index of insertion in the sorted region,
21: // nextItem = next item in the unsorted region.
22: // Initially, sorted region is theArray[0],
23: // unsorted region is theArray[1..n-1].
24: // In general, sorted region is theArray[0..unsorted-1],
25: // unsorted region theArray[unsorted..n-1]
26: for (int unsorted = 1; unsorted < n; unsorted++)
27: {
28: // At this point, theArray[0..unsorted-1] is sorted.
29: // Find the right position (loc) in theArray[0..unsorted]
30: // for theArray[unsorted], which is the first entry in the
31: // unsorted region; shift, if necessary, to make room
32: ItemType nextItem = theArray[unsorted];
33: int loc = unsorted;
34: while ((loc > 0) && (theArray[loc - 1] > nextItem))
35: {
36: // Shift theArray[loc - 1] to the right
37: theArray[loc] = theArray[loc - 1];
38: loc--;
39: } // end while
40:
41: // At this point, theArray[loc] is where nextItem belongs
42: theArray[loc] = nextItem; // Insert nextItem into sorted region
43: } // end for
44: } // end insertionSort
46: int main()
47: {
48: string a[6] = {"Z", "X", "R", "K", "F", "B"};
49: insertionSort(a, 6);
50: for (int i = 0; i < 6; i++)
51: cout << a[i] << " ";
52: cout << endl;
53: } // end main
55: /*
56:
57: B F K R X Z
58:
59: */