// Sort Array Example
// Ch 8
/*
The selection sort algorithm rearranges a list by selecting an element in the list and moving it
to its proper position. This algorithm finds the location of the smallest element in the unsorted
portion of the list and moves it to the top of the unsorted portion of the list. The first time,
we locate the smallest item in the entire list. The second time, we locate the smallest item in
the list starting from the second element in the list, and so on.
*/

#include <iostream>

using namespace std;

// Constant declarations
const int ARRAY_SIZE = 8;

int main()
{
	// Variable declarations
	int list[ARRAY_SIZE] = {16, 30, 24, 7, 62, 45, 5, 55};
	int smallestIndex;
	int temp;
	// Program title and description
	cout << "Selection Sort Example" << endl << endl;

	// Output original unsorted array
	for ( int i = 0; i < ARRAY_SIZE; i++) {
		cout << list[i] << endl;
	}
	cout << endl;
	
	// Outer FOR loop controls current location of the smallest index
	// notice that you iterate to one LESS than the array size
	
	for ( int i = 0; i < ARRAY_SIZE - 1; i++ ) {
		
	

	
		smallestIndex = i; // Find the location of the smallest element
			  // sets smallest value to first item in array
		// Inner FOR loop iterates through the array to compare two values
		
		for (int currentLocation = i+1; currentLocation < ARRAY_SIZE; currentLocation++) {
			// ...if the current value is less than the current smallest value... 
			if (list[currentLocation] < list[smallestIndex]) {
				// ...then set the smallest value to the current value
				smallestIndex = currentLocation;
			}
		}

		// Move the smallest element to the beginning of the unsorted list - note 3 variables needed

		temp = list[smallestIndex];
		list[smallestIndex] = list[i];
		list[i] = temp;
	}	

	// Output sorted array
	
	cout << "Sorted Array: " << endl;
	for ( int i = 0; i < ARRAY_SIZE; i++) {
		cout << list[i] << endl;
	}
	cout << endl;
	
	

	return 0;
}