#include <iostream>
#include <ctime>
using namespace std;

const int n = 100;
int a[n];

int partition(int l, int r)
{
	swap(a[r], a[(l + r) / 2]);
	int indx = l;

	for (int i = l; i < r; i++) if (a[i] < a[r]) swap(a[i], a[indx++]);

	swap(a[r], a[indx]);
	return indx;
}

void quick_sort(int l, int r)
{
	if (l < r)
	{
		int m = partition(l, r);
		quick_sort(l, m - 1);
		quick_sort(m + 1, r);
	}
}

int quick_select(int n, int l, int r)
{
	if (l == r) return a[l];

	int m = partition(l, r);

	if (n == m) return a[m];
	else if (n < m) return quick_select(n, l, m - 1);
	else return quick_select(n, m + 1, r);
}

int main()
{
	srand(time(NULL));
	for (int i = 0; i < n; i++)a[i] = rand() % 100000;

	quick_sort(0, n - 1);
	for (int i = 0; i < n; i++)cout << a[i] << " ";
	cout << endl;

	return 0;
}