1_6_0.cpp

/*//==============================================================================================================
Дано множество целых чисел из [0..10^9] размера n.
Используя алгоритм поиска k-ой порядковой статистики, требуется найти следующие параметры множества:
10%  перцентиль
медиана
90%  перцентиль

Требования: к дополнительной памяти: O(n).
Среднее время работы: O(n)
Должна быть отдельно выделенная функция partition.
Рекурсия запрещена.
Решение должно поддерживать передачу функции сравнения снаружи.


Функцию Partition следует реализовывать методом прохода двумя итераторами в одном направлении. Описание для случая
 прохода от начала массива к концу:
Выбирается опорный элемент. Опорный элемент меняется с последним элементом массива.
Во время работы Partition в начале массива содержатся элементы, не бОльшие опорного. Затем располагаются элементы,
 строго бОльшие опорного. В конце массива лежат нерассмотренные элементы. Последним элементом лежит опорный.
Итератор (индекс) i указывает на начало группы элементов, строго бОльших опорного.
Итератор j больше i, итератор j указывает на первый нерассмотренный элемент.
Шаг алгоритма. Рассматривается элемент, на который указывает j. Если он больше опорного, то сдвигаем j.
Если он не больше опорного, то меняем a[i] и a[j] местами, сдвигаем i и сдвигаем j.
В конце работы алгоритма меняем опорный и элемент, на который указывает итератор i.
Реализуйте стратегию выбора опорного элемента “случайный элемент”. Функцию Partition реализуйте методом прохода двумя
 итераторами от конца массива к началу.
*///==============================================================================================================
#pragma GCC optimize ("Ofast")

#include <iostream>
#include <ctime>

using namespace std;

template <typename T, typename Comparator = greater_equal<T>>
int partition(T *arr, int l, int r, Comparator comp = greater_equal<T>()) {
    if (l != r)
        swap(arr[l + time(nullptr) % (r - l)], arr[l]); // случайный элемент от времени
    T pivot = arr[l];

    int i = r + 1;
    for (int j = r; j >= l; --j) { // проход двумя итераторами от конца массива к началу
        if (comp(arr[j], pivot))
            swap(arr[--i], arr[j]);
    }
    return i;
}
template <typename T, typename Comparator = greater_equal<T>>
T kth_statistic(T *arr, const int k, int l, int r, Comparator comp = greater_equal<T>()){
    for (;;) {
        int pos = partition(arr, l, r, comp);

        if (pos < k)
            l = pos + 1;
        else if (pos > k)
            r = pos - 1;
        else
            return arr[k];
    }
}

int main() {
    int n;
    cin >> n;
    int *arr = new int[n];

    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    cout << kth_statistic(arr, n / 10, 0, n - 1) << endl; // 10% перцентиль
    cout << kth_statistic(arr, n / 2, 0, n - 1) << endl; // медиана (50% перцентиль)
    cout << kth_statistic(arr, n * 9 / 10, 0, n - 1) << endl; // 90% перцентиль

    delete[] arr; // освобождаем память, выделенную под массив
    return 0;
}