#include <cstdio>

#include <algorithm>
#include <vector>
#include <list>
#include <iostream>

void printArray(const int * const a, const int len) {
    for(int i=0; i<len; i++)
        printf("%i ", a[i]);
    printf("\n");
}

template <class T>
void printSeq(T iter, T endIter) {

    while(iter != endIter) {
        std::cout << *iter << " ";
        iter++;
    }
    std::cout << "\n";
}


template <class Titer>
void qsort(const Titer iter, const Titer endIter) {

    if((endIter - iter) < 2)
        return;

    const int len = endIter - iter;

    const int pivot = *(iter + (rand() % len));

    Titer lower = iter;
    Titer upper = endIter - 1;

    while(true) {

        while(*lower < pivot)
            lower++;
        
        while(*upper > pivot)
            upper--;

        // Case where we have two equal elements.
        if(*lower == *upper && lower < upper) {
            lower++;
        }
        
        printSeq(iter, endIter);

        if(lower == upper) {
            break;
        }

        std::swap(*lower, *upper);
    }

    std::cout << "First Part " << "\n";
    printSeq(iter, lower);
    std::cout << "Second Part " << "\n";
    printSeq(lower + 1, endIter);
    std::cout << "\n";

    qsort(iter, lower);
    qsort(lower + 1, endIter);
}

/*

 Without templates..

void qsort(int * const a, const int len) {

    if(len < 2)
        return;

    const int pivot = a[rand() % len];

    printf("Choosed pivot %i\n", pivot);


    int lower = 0;
    int upper = len - 1;

    while(true) {

        while(a[lower] < pivot)
            lower++;
        
        while(a[upper] > pivot)
            upper--;

        // Case where we have two equal elements.
        if(a[lower] == a[upper] && lower < upper) {
            lower++;
        }
        
        printArray(a, len);

        if(lower == upper) {
            break;
        }

        std::swap(a[lower], a[upper]);
    }

    printf("First Part ");
    printArray(a, lower);
    printf("Second Part ");
    printArray(a + lower + 1, len - lower - 1);
    printf("\n");

    qsort(a, lower);
    qsort(a + lower + 1, len - lower - 1);
}
*/

int main() {

    int tmp[] = {1, 7, 3, 6, 11, 0, 0, 5, 7, 2, 9, 2, 4, 8, 12, 1, 10};

    //int tmp[] = {4, 3, 7};

    int len = sizeof(tmp)/sizeof(tmp[0]);

    std::vector<int> a;
    a.assign(tmp, tmp + len);
    qsort(a.begin(), a.end());
    printSeq(a.begin(), a.end());

    /*
    // same using a list
    std::list<int> b;
    a.assign(tmp, tmp + len);
    qsort(b.begin(), b.end());
    printSeq(b.begin(), b.end());
    */

    std::cin.get();
}

1 7 3 6 11 0 0 5 7 2 9 2 4 8 12 1 10 
1 7 3 6 1 0 0 5 7 2 9 2 4 8 12 11 10 
1 7 3 6 1 0 0 5 7 2 8 2 4 9 12 11 10 
First Part 
1 7 3 6 1 0 0 5 7 2 8 2 4 
Second Part 
12 11 10 

1 7 3 6 1 0 0 5 7 2 8 2 4 
1 2 3 6 1 0 0 5 7 2 8 7 4 
1 2 2 6 1 0 0 5 7 3 8 7 4 
1 2 0 6 1 0 2 5 7 3 8 7 4 
1 2 0 2 1 0 6 5 7 3 8 7 4 
1 2 0 0 1 2 6 5 7 3 8 7 4 
First Part 
1 2 0 0 1 
Second Part 
6 5 7 3 8 7 4 

1 2 0 0 1 
0 2 0 1 1 
0 0 2 1 1 
First Part 
0 
Second Part 
2 1 1 

2 1 1 
1 1 2 
First Part 
1 
Second Part 
2 

6 5 7 3 8 7 4 
4 5 7 3 8 7 6 
4 3 7 5 8 7 6 
4 3 5 7 8 7 6 
First Part 
4 3 
Second Part 
7 8 7 6 

4 3 
3 4 
First Part 

Second Part 
4 

7 8 7 6 
6 8 7 7 
6 7 7 8 
First Part 
6 7 
Second Part 
8 

6 7 
First Part 

Second Part 
7 

12 11 10 
10 11 12 
First Part 
10 11 
Second Part 


10 11 
First Part 
10 
Second Part 


0 0 1 1 2 2 3 4 5 6 7 7 8 9 10 11 12