Турнирная сортировка
Cтраница 1
Турнирная сортировка, в той ее форме, которая использует дополнительную память и избегает вычисления адресов, в настоящее время является весьма широко используемым алгоритмом сортировки в программах сортировка-слияние. Из-за большого интереса к турнирной сортировке и ее варианту замещение-выбор, равно как и к ее чисто внутренним версиям, мы здесь продолжим обсуждение организации этой сортировки. [1]
 |
Организация памяти для пяти элементов. [2] |
Последовательные просмотры турнирной сортировки требуют значительно меньше сравнений для выбора победителя. Каждый просмотр этой сортировки ставит одного участника выше оставшихся так, что в конце всех просмотров мы получаем упорядоченный список. На каждом утешительном просмотре используется информация об относительном положении элементов, полученная на предыдущем просмотре, поэтому не надо проводить новый турнир за второе, третье и последующие места. [3]
Один вариант турнирной сортировки размещает исходные признаки в пространстве между записями. Этот прием позволяет, по существу, размещать ключи этих записей отдельно, не разрушая сами записи, причем так, что эти записи можно переписывать из исходной области. [4]
Объем памяти, необходимый для этой версии турнирной сортировки, определяется программным окружением, в котором используется этот метод, и относительной длиной ключа по сравнению с длиной записи. [5]
Более эффективным при внутренней сортировке является метод турнирной сортировки, но его сложнее программировать. Название этого метода объясняется той аналогией, которую он имеет с системой распределения мест в турнире с выбыванием. [6]
Сортировка Флойда по дереву не представляет оптимальную форму турнирной сортировки, поскольку турнир, не использующий вспомогательную адресную память, не будет столь эффективен, как метод, использующий эту память. Однако сортировка Флойда является любопытным минимальным по памяти алгоритмом. Сортировка Шелла включена в этот список, как наилучший из основных методов - вариант просеивания. [7]
 |
Граф турнира в виде двоичного дерева. Узлы со звездочками содержат победителей. [8] |
Турнирная сортировка на самом деле является сортировкой выбором, в которой на каждом просмотре выбирается наименьший элемент из оставшихся в списке. [9]
Турнирная сортировка, в той ее форме, которая использует дополнительную память и избегает вычисления адресов, в настоящее время является весьма широко используемым алгоритмом сортировки в программах сортировка-слияние. Из-за большого интереса к турнирной сортировке и ее варианту замещение-выбор, равно как и к ее чисто внутренним версиям, мы здесь продолжим обсуждение организации этой сортировки. [10]
 |
Четырехпоточное слияние. Вход из 16 строк длиной 1. выход из. [11] |
Способ, используемый для выполнения М - поточного слияния, не всегда столь же прост, как и М-1-поточный способ. В слияниях очень высоких степеней иногда бывает выгодно использовать какую-нибудь форму турнирной сортировки или любой другой эффективный метод для выбора следующего элемента формируемой строки. Ограничение на порядок слияния должно быть таким, чтобы сложность организации М - поточного слияния не превосходила выигрыша при сокращении перемещения данных. [12]
Другая стратегия состоит в организации дерева в виде отделенной таблицы. Все сравнения выполняются на таблице ( сортировка дерева признаков), и обращения к записям нет до тех пор, пока не будет упорядочена таблица признаков. Когда таблица признаков выдает победителя, нужные записи разыскиваются и передаются на выход. Число исключений листов равно вероятности ссылки на нерезидентный лист, умноженной на N. Эта величина значительно ниже уровней неотделенной турнирной сортировки. Если обращение в область записей происходит только при перемещении победителя, то построение строки из 16 победителей вызовет лишь 16 операций листания. [13]
Страницы: 1