// quicksort2.cpp
// Glenn G. Chappell
// 16 Oct 2008
//
// For CS 311 Fall 2009
// Quicksort
// Version #2: Improved
// Uses random-access iterators

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


// insertionSort
// Do Insertion Sort on a given range.
// Requirements on Types:
//     BDIter must be a bidirectional iterator type.
//     operator< must be a total order on the value type of BDIter.
// Pre:
//     [first, last) is a valid range.
// Post:
//     [first, last) contains the same items as it did initially,
//      but now sorted by < (in a stable manner).
template <typename BDIter>
void insertionSort(BDIter first, BDIter last)
{
    // Iterate through the items, inserting each in the proper
    //  place among the earlier items.
    for (BDIter oldPos = first; oldPos != last; ++oldPos)
        // *oldPos = item to insert
    {
        // We need to insert item *oldPos into [first, oldPos].

        // Find the proper location for *oldPos,
        //  using backwards Sequential Search.
        BDIter newPos = oldPos;
        while (newPos != first)
        {
            --newPos;
            if (!(*oldPos < *newPos))  // Stable!
            {
                ++newPos;
                break;
            }
        }
        // Now *oldPos goes at position newPos.
        
        // Rotate other items up and put *oldPos in correct location.
        BDIter afterOldPos = oldPos;
        ++afterOldPos;
        rotate(newPos, oldPos, afterOldPos);
    }
}


// partition
// Partitions a sequence about a given pivot.
// Returns the new pivot position.
// 
// NOTE: This is the partition algorithm in the text.
//
// Requirements on Types:
//     FDIter must be a forward iterator type.
//     operator< must be a total order on the value type of FDIter.
// Pre:
//     [first, last) is a valid nonempty range.
//     pivotIter is an iterator in the range [first, last).
// Post:
//     [first, last) contains the same items as it did initially,
//      but now each ITEM before pivotIter has ITEM < *pivotIter,
//      and each ITEM after pivotIter has !(ITEM < *pivotIter).
//     pivotIter lies in [first, last) and references an item with
//      the same value as *pivotIter before the function call.
template <typename FDIter>
void partition(FDIter first, FDIter last, FDIter & pivotIter)
{
    // Put the pivot at the start of the list
    iter_swap(first, pivotIter);

    // Now "first" points to the pivot

    // Make the "left list": list of items less than pivot
    FDIter leftFinal = first;  // points to final item in left list
    FDIter check = first;      // item to check
    for (++check;              // start after pivot, iterate through list
         check != last;
         ++check)
    {
        if (*check < *first)              // if item < PIVOT
        {
            ++leftFinal;                  // move up end mark
            iter_swap(leftFinal, check);  // and put item in left list
        }
    }

    // Note new pivot position, for caller, and put pivot there
    pivotIter = leftFinal;
    iter_swap(first, pivotIter);
}


// partition_ALT
// Partitions a sequence about a given pivot.
// Returns the new pivot position.
// 
// NOTES:
//   - This is another common parition algorithm.
//   - We could do this with bidirectional iterators, but it gets a
//      little messy.
//
// Requirements on Types:
//     RAIter must be a random-access iterator type.
//     operator< must be a total order on the value type of RAIter.
// Pre:
//     [first, last) is a valid nonempty range.
//     pivotIter is an iterator in the range [first, last).
// Post:
//     [first, last) contains the same items as it did initially,
//      but now each ITEM before pivotIter has !(*pivotIter < ITEM),
//      and each ITEM after pivotIter has !(ITEM < *pivotIter).
//     pivotIter lies in [first, last) and references an item with
//      the same value as *pivotIter before the function call.
template <typename RAIter>
void partition_ALT(RAIter first, RAIter last, RAIter & pivotIter)
{
    // Put the pivot at the start of the list
    iter_swap(first, pivotIter);

    // Now "first" points to the pivot

    // Iterator left: all items before it have !(PIVOT < ITEM)
    RAIter left = first+1;
    // Iterator right: all items after it have !(ITEM < PIVOT)
    RAIter right = last-1;
    // In the loop below, we stop when items before left + items
    //  after right are the entire list.

    while (left <= right)
    {
        // Move left & right in as far as we can
        if (!(*first < *left))        // if *left <= PIVOT
            ++left;
        else if (!(*right < *first))  // if *right >= PIVOT
            --right;
        // If we can move neither left nor right, then swap their items
        else
        {
            iter_swap(left, right);
            ++left;
            --right;
        }
    }

    // Note new pivot position, for caller, and put pivot there
    pivotIter = right;
    iter_swap(first, pivotIter);
}


// quicksort_recurse
// Recursive helper function for quicksort. Nearly sorts a sequence,
//  down to level of SMALL_SIZE, using Quicksort optimized with
//  median-of-three and tail-recursion elimination on the larger
//  recursive call. Sublists of size SMALL_SIZE or smaller are not
//  sorted. Thus, returns data as nearly sorted, ready to be
//  finished with a call to Insertion Sort.
// Recursive.
// Requirements on Types:
//     RAIter must be a random-access iterator type.
//     operator< must be a total order on the value type of RAIter.
// Pre:
//     [first, last) is a valid range.
// Post:
//     [first, last) contains the same items as it did initially,
//      but now nearly sorted by <; sublists of size SMALL_SIZE
//      or smaller may remain unsorted.
template <typename RAIter>
void quicksort_recurse(RAIter first, RAIter last)
{
    while (true)  // Tail-recursion elimination trick
    {
        size_t size = last - first;  // Size of list

        // BASE CASE
        enum { SMALL_SIZE = 8 };     // Max size of "small" sublist
                                     // We do not sort these
        if (size <= SMALL_SIZE)
            return;

        // RECURSIVE CASE

        // Find median-of-three and point pivotIter at it.
        // We do the same comparisons as a Insertion Sort
        // of a 3-item list, but we do not modify the list.
        RAIter middle = first + size/2;
        RAIter finalItem = last-1;
        RAIter pivotIter;
        if (*middle < *first)
        {
            if (*finalItem < *first)
                pivotIter = (*finalItem < *middle) ? middle : finalItem;
            else
                pivotIter = first;
        }
        else
        {
            if (*finalItem < *middle)
                pivotIter = (*finalItem < *first) ? first : finalItem;
            else
                pivotIter = middle;
        }

        // Do partition & recursive sorts
        //  with larger "recursive call" done via iteration
        partition(first, last, pivotIter);
        // NOTE: To use the alternate partition algorithm, replace "partition"
        //  in the above line with "partition_ALT".
        RAIter afterPivot = pivotIter+1;
        if (pivotIter-first < last-afterPivot)
        {
            quicksort_recurse(first, pivotIter);
            first = afterPivot;
        }
        else
        {
            quicksort_recurse(afterPivot, last);
            last = pivotIter;
        }
        // quicksort_recurse(first, last);  // tail recursion eliminated
    }
}


// quicksort
// Sorts a sequence, using Quicksort optimized with median-of-three
//  pivot selection, tail-recursion elimination on the larger
//  recursive call, and an Insertion Sort finish.
// Calls recursive function.
// Requirements on Types:
//     RAIter must be a random-access iterator type.
//     operator< must be a total order on the value type of RAIter.
// Pre:
//     [first, last) is a valid range.
// Post:
//     [first, last) contains the same items as it did initially,
//      but now sorted by <.
template <typename RAIter>
void quicksort(RAIter first, RAIter last)
{
    // Get data nearly sorted
    quicksort_recurse(first, last);

    // Finish with Insertion Sort
    insertionSort(first, last);
}


// main
// Test function quicksort (takes iterators)
int main()
{
    const int SIZE = 11;
    int arr[SIZE] = { 5, 3, 2, 8, 5, 9, 10, 4, 6, 1, -4};
    quicksort(arr, 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;
}