Нахождение k-порядковой статистики.

Определение

Нахождение k-порядковой статистики - это задача, которая заключается в нахождении элемента, занимающего k-ю позицию в отсортированном массиве (изначально массив не отсортирован). Например, если k равно 3, то мы ищем третий элемент в отсортированном массиве.

Один из эффективных алгоритмов для нахождения k-порядковой статистики - это алгоритм QuickSelect, который основан на алгоритме QuickSort. Алгоритм "QuickSelect" работает следующим образом:

1. Выбираем опорный элемент из массива(случайно).
2. Если длина массива 1, возвращаем ответ.
3. Разбиваем массив на два подмассива: элементы, меньшие опорного(левый), и элементы, большие или равные опорному(правый).
4. Если размер левого подмассива элементов, равен k-1, то опорный элемент является k-порядковой статистикой.
5. Если размер  левого подмассива элементов, больше k, то искомый элемент находится в этом подмассиве, рекурсивно применяем алгоритм QuickSelect([подмассив], k).
6. Иначе, искомый элемент находится в правом подмассиве. Рекурсивно применяем алгоритм QuickSelect([подмассив], k-n), где n- длина  левого подмассива.

Алгоритм "QuickSelect" имеет среднюю сложность O(n), где n - размер массива, и является более эффективным, чем полная сортировка массива для нахождения k-порядковой статистики.

Однако, в худшем случае, когда опорный элемент выбирается неудачно, алгоритм "QuickSelect" может иметь сложность O(n^2). Для уменьшения вероятности худшего случая, можно использовать медиану из трех элементов в качестве опорного, либо использовать более сложные стратегии выбора опорного элемента.