1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 11-1.
6: /** Finds the largest item in an array.
7: @pre The size of the array is >= 1.
8: @post The arguments are unchanged.
9: @param theArray The given array.
10: @param size The number of elements in theArray.
11: @return The index of the largest entry in the array. */
12: template <class ItemType>
13: int findIndexOfLargest(const ItemType theArray[], int size);
14: /** Sorts the items in an array into ascending order.
15: @pre None.
16: @post The array is sorted into ascending order; the size of the array
17: is unchanged.
18: @param theArray The array to sort.
19: @param n The size of theArray. */
20: template <class ItemType>
21: void selectionSort(ItemType theArray[], int n)
22: {
23: // last = index of the last item in the subarray of items yet
24: // to be sorted;
25: // largest = index of the largest item found
26: for (int last = n − 1; last >= 1; last––)
27: {
28: // At this point, theArray[last+1..n–1] is sorted, and its
29: // entries are greater than those in theArray[0..last].
30: // Select the largest entry in theArray[0..last]
31: int largest = findIndexOfLargest(theArray, last+1);
32:
33: // Swap the largest entry, theArray[largest], with
34: // theArray[last]
35: std::swap(theArray[largest], theArray[last]);
36: } // end for
37: } // end selectionSort
39: template <class ItemType>
40: int findIndexOfLargest(const ItemType theArray[], int size)
41: {
42: int indexSoFar = 0; // Index of largest entry found so far
43: for (int currentIndex = 1; currentIndex < size; currentIndex++)
44: {
45: // At this point, theArray[indexSoFar] >= all entries in
46: // theArray[0..currentIndex − 1]
47: if (theArray[currentIndex] > theArray[indexSoFar])
48: indexSoFar = currentIndex;
49: } // end for
50:
51: return indexSoFar; // Index of largest entry
52: } // end findIndexOfLargest