#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

void quickSort(int* vect, int p, int q);
int randomized_partition(int*vect, int p, int q);
int partition(int* vect, int p, int q);
void interschimbare(int* x, int* y);

int main(void)
{
	int n, *vect;

	srand((unsigned int)time(0));
	
	ifstream f("algsort.in");
	f>>n;
	vect = new int[n];
	for (int i=0;i<n;i++)
	{
		f>>vect[i];
	}
	f.close();

	quickSort(vect,0,n-1);

	ofstream g("algsort.out");
	for (int i=0;i<n;i++)
	{
		g<<vect[i]<<" ";
	}
	g<<endl;

	delete[] vect;
}

void quickSort(int* vect, int p, int q)
{
	if (p<q)
	{
		int r = randomized_partition(vect,p,q);
		quickSort(vect,p,r-1);
		quickSort(vect,r+1,q);
	}
}

int randomized_partition(int*vect, int p, int q)
{
	int randIdx = p + rand() % (q-p+1);
	interschimbare(&vect[p],&vect[randIdx]);
	return partition(vect,p,q);
}

int partition(int* vect, int p, int q)
{
	int pivot = vect[p];
	int i = p;
	int j;

	for (j=i+1;j<=q;j++)
	{
		if (vect[j] <= pivot)
		{
			i++;
			interschimbare(&vect[i],&vect[j]);
		}
	}
	interschimbare(&vect[p],&vect[i]);
	return i;
}

void interschimbare(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}