#include <iostream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;


bool debug = true;
//bool debug = false;


string int_to_str (const int& x) { 
    ostringstream os; 
    os << x; 
    return os.str(); 
} 


string vec_to_str (vector<int> &nlist, int start, int end)
{
    string out = "";

    for (int i = start; i <= end; i++)
	out += int_to_str(nlist[i]) + "  ";

    return out;
}


void print_list (vector<int> &nlist, int start, int end)
{
    cout << "list:  ";
    cout << vec_to_str (nlist, start, end) << endl;
}

void print_list (vector<int> &nlist)
{
    print_list (nlist, 0, nlist.size()-1);
}


void swap (vector<int> &nlist, int i, int j)
{
    if (debug)
	    cout << "  swapping:  " << nlist[i] << " and " << nlist[j] << endl;

    int tmp = nlist[i];
    nlist[i] = nlist[j];
    nlist[j] = tmp;
}


int get_pivot (int start, int end)
{
    return (start + end) / 2;
}


void quicksort (vector<int>& nlist, int start, int end)
{
    if (debug)
        cout << "quicksort() on sub-list:  " << vec_to_str (nlist, start, end) << endl;

//    if (end <= start)
//        return;

    int i, pivot, l, r;

    pivot = get_pivot (start, end);
    swap (nlist, pivot, end);
    pivot = end;

    if (debug)
        cout << "  after pivot swap:  " << vec_to_str (nlist, start, end) << endl;

    r = end; r--;	// assign right ptr to last element prior to pivot in (sub-) list
    l = start; 		// assign left ptr to first element in (sub-) list

    if (debug)
    {
        cout << "  init:" << endl;
	cout << "    pivot = " << nlist[pivot] << endl;
	cout << "    l = " << nlist[l] << endl;
	cout << "    r = " << nlist[r] << endl;
    }

    while (l < r)
    {
	// move l to first value >= pivot
	while (nlist[l] < nlist[pivot])
	{
	    l++;
	    if (debug)
	        cout << "  l = " << nlist[l] << endl;
	}

	// move l to first value >= pivot
	while (nlist[r] > nlist[pivot])
	{
	    r--;
	    if (debug)
	        cout << "  r = " << nlist[r] << endl;
	}

	// if not pointing to same location, swap
	if (l < r)
	    swap (nlist, l, r);

        if (debug)
            cout << "  list after swap:  " << vec_to_str (nlist, start, end) << endl;
    }

    // once l and r point to same spot, swap pivot with that value, and restore orig end
    swap (nlist, l, pivot);
    pivot = l;

    if (debug)
        cout << "  list after partition:  " << vec_to_str (nlist, start, end) << endl;

    // recurse on left and right sub-lists
    if (start < pivot-1)
	quicksort (nlist, start, pivot-1);

    if (pivot+1 < end)
	quicksort (nlist, pivot+1, end);
}


void quicksort (vector<int>& nlist)
{
    quicksort (nlist, 0, nlist.size()-1);
}


int main()
{
    // the iterator constructor can also be used to construct from arrays:
    int list_inits[] = { 16, 2, 77, 34, 11, 25, 8, 58, 3, 46, 29, 5, 61};

    vector<int> nlist (list_inits, list_inits + sizeof(list_inits) / sizeof(int) );

    cout << "=============================================================================" << endl;

    print_list (nlist);

    quicksort (nlist);

    print_list (nlist);
}