// selection_sort.cpp
// Glenn G. Chappell
// 3 Mar 2008
//
// For CS 311 Spring 2008
// Selection Sort on an Array


#include <iostream>
using std::cout;
using std::endl;
#include <algorithm>  // for std::swap


// selectionSort
// Do Selection Sort on a given array.
// Requirements on Types:
//     operator< must be a total order on T.
//     T must have a copy ctor and copy assignment.
// Pre:
//     p points to an array of at least n items of type T
// Post:
//     p[0 .. n-1] contains the same items as it did initially,
//      but now sorted by <.
template <typename T>
void selectionSort(T p[], int n)
{
    for (int pass = 0; pass < n-1; ++pass)  // Passes
    {
        // Look in p[0] .. p[n-1-pass]
        //  and find the item that goes in position n-1-pass.

        int indexOfBiggest = 0;  // Holds index of biggest item found so far
        for (int i = 1; i <= n-1-pass; ++i)
        {
            if (!(p[i] < p[indexOfBiggest]))
                indexOfBiggest = i;
        }

        // Now p[indexOfBiggest] goes in p[n-1-pass].
        // So put it there, swapping so that the old p[n-1-pass] stays around.
        std::swap(p[indexOfBiggest], p[n-1-pass]);
    }
}


// main
// Test function selectionSort on an array
int main()
{
    const int SIZE = 11;
    int arr[SIZE] = { 5, 3, 2, 8, 5, 9, 10, 4, 6, 1, -4 };
    selectionSort(arr, SIZE);
    for (int i = 0; i < SIZE; ++i)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}