Сортировка с помощью дерева

Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди п элементов, затем среди п-\ элементов и так далее. Улучшить сортировку можно в том случае, если получать от каждого прохода больше информации, чем просто идентификация единственного элемента [1,3,9,10,13]. Например, с помощью п/2 сравнений можно определить наименьший ключ из каждой пары элементов; при помощи следующих п1А сравнений можно выбрать наименьший из каждой пары уже выбранных наименьших ключей; наконец, при помощи п-\ сравнения можно построить дерево выбора и определить корень как наименьший ключ (рис. 3.6).

Рис. 3.6. Повторяющиеся наборы среди двух ключей

На втором шаге спускаемся по пути, указанному наименьшим ключом и исключаем его, последовательно заменяя на «дыру», либо на элемент, находящийся на противоположной ветви промежуточного узла (рис. 3.7).

Элемент, оказавшийся в корне дерева, вновь имеет наименьший ключ и может быть исключен. После п шагов дерево становится пустым, и процесс сортировки заканчивается. Каждый из п шагов требует logw сравнений. Поэтому вся сортировка требует n-\og2ⁿ операций, не считая п шагов на построение дерева. Это значительное улучшение по сравнению с прямым методом выбора, который

требует п шагов, но и даже по сравнению с сортировкой Шелла, которая требует п ' шага.