// insertion_sort.cpp
// Glenn G. Chappell
// 9 Oct 2009
//
// For CS 311 Fall 2009
// Insertion Sort on an Array

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <algorithm>
using std::rotate;


// insertionSort
// Do Insertion 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 < (in a stable manner).
template <typename T>
void insertionSort(T p[], int n)
{
    // Iterate through the items, inserting each in the proper
    //  place among the earlier items.
    for (int i = 1; i < n; ++i)  // i = index of item to insert
    {
        // We need to insert item i into p[0..i-1].

        // Find the proper location for p[i],
        //  using backwards Sequential Search.
        int k;
        for (k = i-1; k >= 0; --k)
        {
            if (!(p[i] < p[k]))  // Stable!
                break;
        }
        // Now p[i] goes *after* index k, that is, at index k+1,
        //  even if we fell off the end of the loop, and k is -1.
        
        // Rotate other items up and put p[i] in correct location.
        rotate(p+(k+1), p+i, p+(i+1));
        // The above line replaces the following code:
        //  T saveItem = p[i];
        //  for (int m = i-1; m > k; --m)
        //      p[m+1] = p[m];
        //  p[k+1] = saveItem;
    }
}


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

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}