Задача выбора

Формулирование задачи. В заданном линейном списке целых чисел B={K1,K2,...,Kn} (могут быть и одинаковые) необходимо найти элемент, который был бы расположен на i-ой позиции, если бы список B упорядочить по убыванию элементов. Это задача выбора i-ого наибольшего значения. В частности, для i=1 задача эквивалентна поиску в B элемента с наибольшим значением, для i=2 - поиск элемента со вторым наибольшим значением и т.д. Особый интерес вызывает задача выбора i-ого элемента, i= an, 0 <a< 1 для некоторых значений a, например, выбор медианы при a=1/2.

Алгоритм поиска наибольшего значения легко меняется на алгоритм поиска наименьшего значения.

Все варианты задачи выбора развязываются легко, если список B полностью отсортированный; тогда задача сводится до взятия в нём необходимого элемента.

Для развязывания задачи выбора i-ого наибольшего элемента в списке B={K1,K2,...,Kn} модифицирован алгоритм быстрой сортировки. Список делится элементом K1 на подсписки B1и B2, такие, что когда K принадлежит B1, то K>=K1, а когда K принадлежит B2, то K<K1. Список B реорганизуется в список B1,<K1>,B2, в котором K1 находится ан j-ом месте. Если j=i, то необходимый элемент найден; если j>i, то i-ое наибольшее значение ищется с подсписке B1; если j<i, то (i-j)-ое наибольшее значение ищется с подсписке B2.

Алгоритм выбора. Алгоритм на базе быстрой сортировки довольно эффективный для его выполнения необходимо количество действий порядка О(n). По некоторым причинам он может стать неэффективным, вымогая для своей реализации количества действий порядка O(n*n). Неэффективность объясняется тем, что K1 делит список B на неравные подсписки B1 и B2. Для улучшения алгоритма необходимо уметь находить в списке B элемент M, который разделяет список почти поровну.