gistfile1.cpp

#include <algorithm>  // iter_swap
#include <vector>
#include <assert.h>

using namespace std;


template<typename IT>
bool is_sorted(IT begin, IT end)
{
    if (begin == end)
        return true;
    for (auto it = begin + 1; it != end; begin = it, ++it) {
        if (*it < *begin)
            return false;
    }
    return true;
}


template<typename T>
vector<T> & operator<<(vector<T> &s, T v)
{
    s.push_back(v);
    return s;
}


template<typename IT>
void quicksort(IT const begin, IT const end)
{
    auto length = end - begin;
    if (length < 2)
        return;
    auto pivot = *(begin + length / 2);
    //auto pivot = *begin;
    IT left = begin;
    IT right = end;
    while (true) {
        while (*left < pivot) {
            ++left;
        }
        --right;
        while (pivot < *right) {
            --right;
        }
        if (left >= right) {
            break;  // left is partition splitter
        }
        iter_swap(left, right);
        ++left;
    }
    quicksort(begin, left);
    quicksort(left, end);
}


int main()
{
    //vector<int> v1 = {8, 1, 7, 9, 4, 5, 3, 0, 5, 2, 3};
    vector<int> v1; v1 << 8 << 1 << 7 << 9 << 4 << 5 << 3 << 0 << 5 << 2 << 3;
    assert(!is_sorted(v1.begin(), v1.end()));
    quicksort(v1.begin(), v1.end());
    assert(is_sorted(v1.begin(), v1.end()));
    return 0;
}