#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define NMAX 100

int n = 10;
void swap(int *p, int *q) {
	int tmp = *p;
	*p = *q;
	*q = tmp;
}


void print(FILE *g, int *v, int n) {
	int i;
	for (i =  1; i <= n; i++) {
		fprintf(g, "%d%c", v[i] , (i<n? ' ' : '\n' ));
	}
}
/*
10
1 2 3 4 5 6 7 8 9 10
3 8 1 3 3 1 8 1 3 1
*/
int partition(int *v, int p, int q) {
	int poz ;
	int pivot = v[p];//poz = p + rand() % (q-p+1)];
	int i = p, j = q;
	while (i < j) {
		while (i < j && i <= q && v[i] < pivot) i++;
		while (i < j && pivot <= v[j]) j--;
		if (i < j) {
			swap(&v[i], &v[j]);
			i++;
			j--;
		} else {
			return j;
		}
	}
}

void quickSort(int *v, int p, int q) {
	if (p < q) {
		int pivotPosition = partition(v, p , q);
		assert(p <= pivotPosition && pivotPosition <= q);
		quickSort(v, p, pivotPosition);
		quickSort(v, pivotPosition+1, q);
	}
}

int main() {
	FILE *f = fopen("algsort.in", "r");
	FILE *g = fopen("algsort.out", "w");

	srand(time(NULL));

	int n, *v,i;
	fscanf(f,"%d", &n);
	v = (int *)malloc((n+1) * sizeof(int));
	
	for (i =  1; i <= n; i++) {
		fscanf(f,"%d", &v[i]);
	}
	// print(g, v, n);

	quickSort(v, 1, n);
	print(g, v, n);
	free(v);
	return 0;
}