//
// demonstrates a selection sort
// Written by Maxwell Sayles, 2001, for CPSC331, University of Calgary.
//

#include <stdlib.h>
#include <time.h>

#include <iostream>
using namespace std; 

const int numElements = 128; // number of elements to sort


//
//
// This routine sorts an array of integers in ascending order.
//
// The algorithm is taken from pp. 2-4.
//		Cormen, Thomas H., et al.  Introduction to Algorithms.  
//		The MIT Press, 1990.
//
void SelectionSort (int* a, const int n)
{
	for (int i = 0;  i < n;  i ++)
	{
		int j = i;
		// find smallest integer in a[i] to a[n-1]
		for (int k = i + 1;  k < n;  k ++)
			if (a[k] < a[j]) j=k;
		// interchange
		int temp = a[i]; a[i] = a[j]; a[j] = temp;
	}
}


//
// program entry
//
int main()
{
	int i = 0;

	// seed the random number generator
	srand(time(0));

	// create an array of random integers
	int array[numElements];
	for (i = 0;  i < numElements;  i = i + 1)
	{
		array[i] = rand() % numElements; // keep numbers in the range of 0-numElements
	}

	// sort the array
	SelectionSort (array, numElements);

	// print the array
	for (i = 0;  i < numElements;  i = i + 1)
	{
		cout << array[i] << ' ';
	}
	cout << endl;

	return 0;
}