1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: // Listing 11-1.
6: #include <iostream>
7: #include <string>
9: using namespace std;
10: template<class ItemType>
12: /** Finds the largest item in an array.
13: @pre The size of the array is >= 1.
14: @post The arguments are unchanged.
15: @param theArray The given array.
16: @param size The number of elements in theArray.
17: @return The index of the largest entry in the array. */
18: int findIndexofLargest(const ItemType theArray[], int size);
20: /** Sorts the items in an array into ascending order.
21: @pre None.
22: @post The array is sorted into ascending order; the size of the array
23: is unchanged.
24: @param theArray The array to sort.
25: @param n The size of theArray. */
26: void selectionSort(ItemType theArray[], int n)
27: {
28: // last = index of the last item in the subarray of items yet
29: // to be sorted;
30: // largest = index of the largest item found
31: for (int last = n - 1; last >= 1; last--)
32: {
33: // At this point, theArray[last+1..n-1] is sorted, and its
34: // entries are greater than those in theArray[0..last].
35: // Select the largest entry in theArray[0..last]
36: int largest = findIndexofLargest(theArray, last+1);
37:
38: // Swap the largest entry, theArray[largest], with
39: // theArray[last]
40: std::swap(theArray[largest], theArray[last]);
41: } // end for
42: } // end selectionSort
44: int findIndexofLargest(const ItemType theArray[], int size)
45: {
46: int indexSoFar = 0; // Index of largest entry found so far
47: for (int currentIndex = 1; currentIndex < size; currentIndex++)
48: {
49: // At this point, theArray[indexSoFar] >= all entries in
50: // theArray[0..currentIndex - 1]
51: if (theArray[currentIndex] > theArray[indexSoFar])
52: indexSoFar = currentIndex;
53: } // end for
54: return indexSoFar; // Index of largest entry
55: } // end findIndexofLargest
57: int main()
58: {
59: string a[6] = {"Z", "X", "R", "K", "F", "B"};
60: selectionSort(a, 6);
61: for (int i = 0; i < 6; i++)
62: cout << a[i] << " ";
63: cout << endl;
64: } // end main
66: /*
68: B F K R X Z
70: */