BC/NW 2015 № 1 (26) 6:1
ИСПОЛЬЗОВАНИЕ СХЕМЫ
ТУРНИРА С ВЫБЫВАНИЕМ ПРИ СЛИЯНИИ УПОРЯДОЧЕННЫХ ЧАСТЕЙ МАССИВА
Белякова
Е.М., Зубов В.С.
Схема
турнира явилась прообразом широко используемой пирамидальной сортировки [1],
предлагаем применять ее также для рациональной организации слияния t частей
массива (t-арное слияние). Здесь главной проблемой является минимизация числа M
сравнений при выборе каждой записи в результат слияния, теоретический минимум
≈ log 2 t, а всего за слияние ≈ n log 2 t, где n – общее число
записей (ключей), участвующих в слиянии.
Пусть
части массива упорядочены по возрастанию ключей. В схему выбора, являющуюся
бинарным деревом, сначала загружаются t ссылок на первые записи частей. Это
листья дерева. В результате сравнений по принципу турнира с выбыванием в корень
дерева поднимается ссылка на минимальную запись, передаваемую в результат. Эта
ссылка увеличивается на 1, что означает переход к следующей записи той части,
из которой извлекли минимальную запись. «Турнир» повторяется, в корень поднимается
ссылка на вторую по величине запись и т.д.
Если
выбранная запись последняя в своей части, ссылка на нее в дереве заменяется
ссылкой на ∞, тем самым блокируется выбор в опустевшей
части. После рассмотрения всех n записей все узлы дерева станут ссылками на ∞.
Примечательно, что даже в случае исчерпания всех частей, кроме одной, выбор
записи по-прежнему требует прохождения трассы от листа до корня дерева. При
больших частях это не приводит к заметным издержкам времени, зато упрощает
алгоритм и оценку среднего числа M сравнений.
Значение
M, очевидно, равно log 2 t при t = 2k . При других k схема турнира отличается
от «классической». Дерево ссылок размещается в памяти наподобие дерева в
пирамидальной сортировке и является полным деревом [2]. Для него значение M
может быть найдено по методике получения длины внешнего пути, изложенной в [2].
Применение
схемы турнира в t-арном слиянии минимизирует общее число сравнений и выдвигает
метод t-арного слияния в лидеры при сортировке больших массивов данных.
Литература
1. Кнут
Д.Э. Искусство программирования. Т. 3. Сортировка и поиск: пер. сангл. – 2-е
изд. М.: Издательский дом «Вильямс», 2000.
2. Кнут
Д.Э. Искусство программирования. Т. 1. Основные алгоритмы: пер. с англ. – 3-е
изд. М.: Издательский дом «Вильямс», 2001.