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.