// quicksort1.cpp
// Glenn G. Chappell
// 17 Mar 2008
//
// For CS 311 Spring 2008
// Quicksort
// Version #1: Basic
// Uses forward iterators

#include <iostream>
using std::cout;
using std::endl;
#include <algorithm>  // For std::iter_swap


// 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
    std::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
            std::iter_swap(leftFinal, check);  // and put item in left list
        }
    }

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


// partition_ALT
// Partitions a sequence about a given pivot.
// Returns the new pivot position.
// 
// NOTE: This is another common parition algorithm.
//
// 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
    std::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
        {
            std::iter_swap(left, right);
            ++left;
            --right;
        }
    }

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


// quicksort
// Sorts a sequence, using Quicksort.
// Recursive.
// 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 range.
// Post:
//     [first, last) contains the same items as it did initially,
//      but now sorted by <.
template <typename FDIter>
void quicksort(FDIter first, FDIter last)
{
    // BASE CASE
    if (first == last)
        return;

    // RECURSIVE CASE

    // Simple pivot choice: pick the first item
    FDIter pivotIter = first;

    // Do partition & recursive sorts
    partition(first, last, pivotIter);
    // NOTE: To use the alternate partition algorhtm, replace "partition"
    //  in the above line with "partition_ALT".
    quicksort(first, pivotIter);
    ++pivotIter;
    quicksort(pivotIter, 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;

   return 0;
}