/*	Selection Sort program */

#include <stdlib.h>
#include <iostream.h>
#include <lvpvector.h>
#include <lvprandom.h>

using namespace std;	// October 5, 2001

typedef lvpvector<int> ArrayType;

//--------------------------------------------------------------------------------
int FindLowest(const ArrayType &A)
/*	Returns the index of the lowest value in the array.
	Post: Index of lowest value in array returned         */
{
	int LowSpotSoFar = 0;
	for (int i=1; i<A.length(); i++) {
		if (A[i] < A[LowSpotSoFar])
			LowSpotSoFar = i;
		}
	return(LowSpotSoFar);
}
//--------------------------------------------------------------------------------
void AddToArray(ArrayType &A, const int NewItem)
/*	Increases size of A by 1 and adds NewItem to A
	Post: Size of A increased by 1, NewItem last element in A */
{
	A.resize(A.length()+1);
	A[A.length()-1] = NewItem;
}
//--------------------------------------------------------------------------------
void RemoveFromArray(ArrayType &A, int Index)
/*	Removes element A[Index] by sliding later elements back.
	Assumes 0 <= Index < A.length()-1
	Post: A[Index] deleted, size of A decreased by 1                 */
{
	for (int i=Index; i<A.length()-1; i++)
		A[i] = A[i+1];
	A.resize(A.length()-1);
}
//--------------------------------------------------------------------------------
void SelectionSort(ArrayType &A)
/*	Sorts A from low to high
	Post: Elements of A in order from low to high */
{
	ArrayType Temp(0);
	while (A.length() != 0) {
		int LowSpot = FindLowest(A);
		AddToArray(Temp, A[LowSpot]);
		RemoveFromArray(A, LowSpot);
	}
	A = Temp;
}
//--------------------------------------------------------------------------------
void LoadRandomArray(ArrayType &A, int Size)
/*	Fills array A with Size random values in the range 0..999 */
{
	const int MaxValue = 999;
	A.resize(Size);
	for (int i=0; i<Size; i++)
		A[i] = lvprandom(MaxValue+1);
}
//--------------------------------------------------------------------------------
void DisplayArray(const ArrayType &A)
/*	Displays the items of A, with field width of 5, 10 per line */
{
	for (int i=0; i<A.length(); i++) {
		cout.width(5); cout << A[i];
		if ((i+1)%10 == 0)
			cout << endl;
	}
	cout << endl;
}
//--------------------------------------------------------------------------------
void Sort (ArrayType &A)
/*	Sorts array A from low to high */
{
	SelectionSort(A);
}
//--------------------------------------------------------------------------------
int main()
{
	randomize();
	ArrayType Sample;
	const int SampleSize = 20;
	LoadRandomArray(Sample, SampleSize);
	DisplayArray(Sample);
	Sort(Sample);
	DisplayArray(Sample);
	return(0);
}