// quicksort.cpp 
 
#include "stdafx.h"
 
#include <iostream>
#include <string>
#include <cassert>
#include <cstdlib> // srand ()
#include <ctime> // time ()
using namespace std;
 
const int N = 1000000;
 
int a[N];
 
void swap (int &x, int &y) {
	int z = x;
	x = y;
	y = z;
}
 
void change (int i, int j) {
	int z = a[i];
	a[i] = a[j];
	a[j] = z;
}
 
void quick (int r, int s)
{
	int h = a[(r+s)/2];
	int i = r;
	int j = s;
 
	// cout << "quick (" << r << "," << s << ", h=" << h<< "): ";
	// 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--;
		if (i<j) swap (a[i], a[j]);
  	        // if (i<j) {
                // cout << "swap (" << i << "," << j << "): ";
	        // for (int k = r; k <= s; k++) cout << a[k] << ",";
	        // cout << endl;
                // }
		if (i<=j) { i++; j--; }	
	}
	if(r<j) quick (r,j);
	if(i<s) quick (i,s);
}
 
void quicksort (int n)
{
	quick(0,n-1);
}
 
void init (int n){
	srand (time (NULL));
	for(int i=0; i< n; i++)
		a[i] = rand () % (n);
}
 
void vypis (int n){
	for(int i=0; i< n; i++)
		cout << a[i] << " ";
	cout << endl;
}
 
void kontrola (int n)
{
	for(int i=0; i< n-1; i++)
		assert (a[i]<=a[i+1]);
}
 
int _tmain(int argc, _TCHAR* argv[])
{
	int n = 10;
	assert (n <= N);
	init (n);
	if (n <= 1000) vypis (n);
	quicksort (n);
	if (n <= 1000) vypis (n);
	kontrola (n);
	system ("pause");
	return 0;
}