Сортировку выбора можно значительно ускорить если сохранять после каждого поиска минимума какие то значения, которые ускорят поиск следующего минимального. Одним из путей будет построение дерева выбора. Исходный массив будет являться листьями дерева. Листья попарно объединяем и в новый узел выносим максимальный из двух, таким образом получается второй ярус. Этот ярус так же попарно объединяем и т.д. , пока не останется один элемент, который и будет корнем дерева. В корне будет максимальное значение . Этот элемент мы удаляем из корня и ищем следующий максимальный за исключением корня. Это можно сделать за меньшее число сравнений.
Достаточно спуститься от корня к листьям тем путем, каким значение попало в корень. Для этого достаточно найти среди двух потомков равные ему и перейти, повторять операцию до тех пор, пока не дойдем до листьев. Лист удаляем, после этого поднимаемся снова к корню в поимке нового максимального значения.
Достоинство: высокая скорость, приближенная к скорости сортировки Хоара.
Недостаток: требуется много памяти.
Похожие записи
No user прокомментировали сообщение
Оставить комментарий