// Chapter 9, p407
#include <stdlib.h> // included for rand in main
#include <iostream.h>

const int MAX_SIZE = 12;

typedef int dataType;  // type-of-array-item
typedef dataType arrayType[MAX_SIZE];

int IndexOfLargest(const dataType A[], int Size);
void Swap(dataType& X, dataType& Y);

void SelectionSort(dataType A[], int N)
// ---------------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: A is an array of N items.
// Postcondition: The array A is sorted into ascending 
// order; N is unchanged.
// Calls: IndexOfLargest, Swap.
// ---------------------------------------------------------
{
	// Last is the index of the last item in the subarray,
   // L is the index of the largest item found

   for (int Last = N-1; Last >= 1; --Last)
   {  // Invariant: A[Last+1..N-1] is sorted and >
		// A[0..Last]

      // select largest item in A[0..Last]
      int L = IndexOfLargest(A, Last+1);

      // swap largest item A[L] with A[Last]
		Swap(A[L], A[Last]);
	}  // end for
}  // end SelectionSort

int IndexOfLargest(const dataType A[], int Size)
// ---------------------------------------------------------
// Finds the largest item in an array.
// Precondition: A is an array of Size items, Size >= 1.
// Postcondition: Returns the index of the largest item 
// in the array. The arguments are unchanged.
// ---------------------------------------------------------
{
   int IndexSoFar = 0;  // index of largest item found so far

	for (int CurrentIndex = 1; CurrentIndex < Size;
										++CurrentIndex)
	{  // Invariant: A[IndexSoFar] >= A[0..CurrentIndex-1]
		if (A[CurrentIndex] > A[IndexSoFar])
			IndexSoFar = CurrentIndex;
	}  // end for

	return IndexSoFar;  // index of largest item
}  // end IndexOfLargest

void Swap(dataType& X, dataType& Y)
// ---------------------------------------------------------
// Swaps X and Y.
// Precondition: None.
// Postcondition: Contents of actual locations that X and Y
// represent are swapped.
// ---------------------------------------------------------
{
	dataType Temp = X;
	X = Y;
	Y = Temp;
}  // end Swap

// ******SAMPLE MAIN PROGRAM******
main()
{  arrayType A;
   int N, Size;

   // create an array of random integers
   Size = MAX_SIZE; // size of array
   for (N = 0; N < Size; ++N)
      A[N] = rand();

	cout << "The array before sorting is:\n ";
	for (N = 0; N < Size; ++N)
		cout << A[N] << " ";
	cout << "\n";

	// sort the array
	SelectionSort(A, Size);

	cout << "The array after sorting is:\n ";
	for (N = 0; N < Size; ++N)
		cout << A[N] << " ";
	cout << "\n";
	return 0;
}  // end main