/*Напишите эффективную функцию находящую k-ую порядковую статистику в массиве. Программа должна состоять из этой функции и примера её использования в main.*/




#include <iostream>
using namespace std;

int findOrderStatistic(int * a, int n, int k) {
	int left = 1, right = n;
	while (true) {
		if (right <= left + 1) {
			if (right == left + 1 && a[right] < a[left]) {
				swap (a[left], a[right]);
			}
			return a[k];
		}

		// упорядочиваем a[left], a[left + 1], a[right]
		int mid = (left + right) >> 1;
		swap(a[mid], a[left + 1]);
		if (a[left] > a[right]) {
			swap (a[left], a[right]);
		} if (a[left + 1] > a[right]) {
			swap (a[left + 1], a[right]);
		} if (a[left] > a[left + 1]) {
			swap(a[left], a[left + 1]);
		}

		// выполняем разделение
		// барьером является a[left + 1], т.е. медиана среди a[left], a[left + 1], a[right]
		int i = left + 1;
		int j = right;
		int current = a[left + 1];
		while (true) {
			while (a[++i] < current);
			while (a[--j] > current);
			if (i > j) {
				break;
			}
			swap(a[i], a[j]);
		}

		// вставляем барьер
		a[left + 1] = a[j];
		a[j] = current;

		// продолжаем работать в той части,
		// которая должна содержать искомый элемент
		if (j >= k) {
			right = j - 1;
		} if (j <= k) {
			left = i;
		}
	}
}

int main() {
	int a[] = {1, 3, 5, 7, 7};
	cout << findOrderStatistic(a, 5, 3);

	return 0;
}