Может ли QuickSelect найти наименьший элемент в массиве с повторяющимися значениями?

Question

Работает ли алгоритм QuickSelect с дублирующимися значениями?

Если у меня есть массив

int[] array = {9, 8, 7, 6, 6, 6, 5, 0, 1, 2, 3, 4, 5, 5, 7, 200};

Сможет ли он получить k-й наименьший элемент, даже если есть дубликаты?

Answer 1

Да, это работает. К концу каждой итерации все элементы, меньшие текущей сводки, сохраняются слева от сводки.

Рассмотрим случай, когда все элементы одинаковы. В этом случае каждая итерация заканчивается размещением элемента pivot слева от массива. И следующая итерация будет продолжена с одним элементом более короткого массива. Итак, нам нужно k итерации для нахождения k-го наименьшего элемента.