// quick.cpp 
 
#include "stdafx.h"
 
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
 
const int N = 1000000;
int a [N];
 
void swap(int &c, int &k){
    int pom;
    pom=c;
    c=k;
    k=pom;
}
 
void quick (int r, int s){
    int i=r;
    int j=s;
    int h = a[(r+s)/2];
 
    // cout << "quick (" << r << "," << s << ") :" << h << ":" << endl;
	// for (int k=r; k<=s; k++) cout << a[k] << ", ";
    // cout << endl;
 
    while (i <= j)
    {
        while (a[i]<h) i++;
        while (a[j]>h) j--;
        // cout << "swap " << i << "," << j << ":" << a[i] << ":" << a[j] << endl;
        if (i < j) 
		{
			swap (a[i],a[j]);
		}
        if (i <= j) 
		{
			i++;
            j--; 
		}
  	    // for (int k=r; k<=s; k++) cout << a[k] << ", ";
        // cout << endl;
    }
    // cout << "end swap " << r << "," << j << "," << i << "," << s << endl;
    // cout << endl << "........" << endl << endl;
 
    if (r < j) quick (r, j);
    if (i < s) quick (i, s);
}
 
void quicksort(int n)
{
    assert (n <= N && n > 0);
    quick(0, n - 1);
};
 
void vypis(int n)
{
    for (int i=0; i<n; i++)
    {
        cout << a[i] << ", ";
    }
    cout << endl;
};
 
void kontrola(int n)
{
    for(int i=1; i<n; i++)
    {
       assert (a[i-1] <= a[i]);
    }
};
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int n = 100;
    assert (n <= N);
 
    for (int i=0; i<N; i++)
        a[i] = -1;
 
    for (int i=0; i<n; i++)
        a[i] = rand () % (n/2);
 
    if (n <= 1000) vypis (n);
    cout << " ----- " << endl;
    quicksort (n);
    if (n <= 1000) vypis (n);
    kontrola (n);
 
    system ("pause");
    return 0;
}