Продолжаем знакомиться с разнообразными кучами и алгоритмами сортировок с помощью этих куч. Сегодня у нас так называемое турнирное дерево.
Основная идея Tournament sort заключается в использовании относительно небольшой (по сравнению с основным массивом) вспомогательной кучи, которая выполняет роль приоритетной очереди. В этой куче сравниваются элементы на нижних уровнях, в результате чего меньшие элементы (в данном случае дерево у нас MIN-HEAP) поднимаются наверх, а в корень всплывает текущий минимум из той порции элементов массива, которые попали в эту кучу. Минимум переносится в дополнительный массив «победителей», в результате чего в куче происходит сравнение/перемещение оставшихся элементов — и вот уже в корне дерева новый минимум. Отметим, что при такой системе очередной минимум по значению больше чем предыдущий — тогда легко собирается новый упорядоченный массив «победителей», где новые минимумы просто добавляются в конец дополнительного массива.
Мы в EDISON часто разрабатываем умные алгоритмы в наших проектах.
Например, для одного заказчика был разработан специальный способ передачи данных с помощью светодиода. Изначально заказчик планировал поиск и анализ конкретного светового пятная в видеопотоке, однако мы предложили более элегантное и надёжное решение.
Мы очень любим computer science ;-)
Перенос минимумов в дополнительный массив приводит к тому, что в куче появляются вакантные места для следующих элементов основного массива — в результате чего в порядке очереди обрабатываются все элементы.
Главной тонкостью является то, что кроме «победителей» есть ещё и «проигравшие». Если в массив «победителей» уже перенесены какие-то элементы, то если необработанные элементы меньше, чем эти «победители» то просеивать их через турнирное дерево на этом этапе уже нет смысла — вставка этих элементов в массив «победителей» будет слишком дорогой (в конец их уже не поставишь, а чтобы поставить в начало — придётся сдвинуть уже вставленные раннее минимумы). Такие элементы, не успевшие вписаться в массив «победителей» отправляются в массив «проигравших» — они пройдут через турнирное дерево в одной из следующих итерации, когда все действия повторяются для оставшихся неудачников.
В Интернете непросто найти реализацию этого алгоритма, однако в Ютубе обнаружилась понятная и симпатичная реализация на Руби. В разделе «Ссылки» ещё упомянут код на Java, но там выглядит не настолько читабельно.
# Библиотека для работы с приоритетной очередью в виде кучи
require_relative "pqueue"
# Максимальный размер для приоритетной очереди
MAX_SIZE = 16
def tournament_sort(array)
# Если массив маленький, то упрощённый "турнир"
return optimal_tourney_sort(array) if array.size <= MAX_SIZE
bracketize(array) # Если массив большой, то стандартный "турнир"
end
# Пропускаем элементы через турнирную сетку
def bracketize(array)
size = array.size
pq = PriorityQueue.new
# Заполняем очередь первыми элементами
pq.add(array.shift) until pq.size == MAX_SIZE
winners = [] # Сбор "победителей"
losers = [] # Сбор "проигравших"
# Пока в основном массиве есть элементы
until array.empty?
# Массив "победителей" пока пуст?
if winners.empty?
# Из корня переносим в массив "победителей"
winners << pq.peek
# Восстановление кучи после переноса корня
pq.remove
end
# Если очередной элемент из массива больше, чем последний "победитель"
if array.first > winners.last
pq.add(array.shift) # Переносим элемент в очередь на вакантное место
else # Если очередной элемент меньше или равен последнему "победителю"
losers << array.shift # Переносим элемент в массив "проигравших"
end
# Если куча пока не пуста, корень переносим в массив "победителей"
winners << pk.peek unless pk.peek.nil?
pq.remove # Восстановление кучи после переноса корня
end
# Основной массив пуст, но может в куче ещё что-то осталось?
until pq.heap.empty?
winners << pq.peek # Корень переносим в массив "победителей"
pq.remove # Восстановление кучи после переноса корня
end
# Если массив "проигравших" остался пуст, то, значит,
# массив "победителей" - итоговый отсортированный массив
return winners if losers.empty?
# Если ещё не закончили, то к массиву "проигравших"
# припишем массив "победителей"
array = losers + winners
array.pop while array.size > size
bracketize(array) # Запускаем процесс снова
end
# Упрощённый турнир если массив меньше чем очередь
def optimal_tourney_sort(array)
sorted_array = [] # Заготовка для отсортированного массива
pq = PriorityQueue.new
array.each { |num| pq.add(num) } # Переносим все элементы в мини-кучу
until pq.heap.empty? # Пока мини-куча не пуста
sorted_array << pq.heap[0]
pq.remove # Восстановление кучи после переноса корня
end
sorted_array # Итоговый массив
end
# Тестирование
if $PROGRAM_NAME == __FILE__
# Генерируем массив
shuffled_array = Array.new(30) { rand(-100 ... 100) }
# Печать необработанного массива
puts "Random Array: #{shuffled_array}"
# Печать обработанного массива
puts "Sorted Array: #{tournament_sort(shuffled_array)}"
endЭто наивная реализация, в которой после каждого разделения на «проигравших» и «победителей» эти массивы объединяются и затем для объединённого массива все действия повторяются снова. Если в объединённом массиве будут сначала идти «проигравшие» элементы, то просейка через турнирную кучу упорядочит их совместно с «победителями».
Данная реализация достаточно проста и наглядна, но эффективной её не назовёшь. Отсортированные «победители» проходят через турнирное дерево неоднократно, что выглядит, очевидно, излишним. Предполагаю, что временна́я сложность здесь логарифмично-квадратичная,
Вариант с многопутевым слиянием
Алгоритм заметно ускоряется, если прошедшие через сито упорядоченные элементы не пропускать через турнирные забеги повторно.
После того как неупорядоченный массив разделится на отсортированных «победителей» и неотсортированных «проигравших», весь процесс заново повторяем только для «проигравших». На каждой новой итерации будет накапливаться набор массивов с «победителями» и так будет продолжаться до тех пор, пока на каком-то шаге «проигравших» уже не останется. После чего останется только произвести слияние всех массивов «победителей». Так как все эти массивы отсортированы, это слияние проходит с минимальными затратами.
В таком виде алгоритм может уже вполне найти полезное применение. Например, если приходится работать с big data, то по ходу процесса с помощью турнирной кучи будут выходить пакеты упорядоченных данных, с которыми уже можно что-нибудь делать, пока обрабатывается и всё остальное.
Каждый из n элементов массива проходит через турнирное дерево всего один раз, что обходится в
В финале сезона
Серия статей о сортировках кучей почти завершена. Осталось рассказать о самой эффективной из них.
Ссылки
Tournament sort
Priority queue
Tournament sort in Java
The Theory Behind the The Theory Behind the z/Architecture Sort Assist Instructions
Using Tournament Trees to Sort
Tournament Sort Demo Ruby Tournament Sort Visualization Tournament Sort Data Structure UGC NET DS Tournament Sort Algorithm — a Heapsort variantСтатьи серии:
- Excel-приложение AlgoLab.xlsm
- Сортировки обменами
- Сортировки вставками
- Сортировки выбором
- Сортировки слиянием
- Сортировки распределением
- Гибридные сортировки
В приложение AlgoLab добавлена сегодняшняя сортировка, кто пользуется — обновите excel-файл с макросами.
В комментариях к ячейке с название сортировки можно указать некоторые настройки.
Переменная way — скольки-путевое турнирное дерево (просто на всякий случай предусмотрена возможность делать это дерево не только двоичным, но и троичным, четверичным и пятиричным).
Переменная queue — это размер первоначальной очереди (количество узлов в самом нижнем уровне дерева). Так как деревья полные, то если, к примеру при way=2 указать queue=5, то размер очереди будет увеличен до ближайшей степени двойки (в данном случае до 8).
Переменная NWayMerge принимает значение 1 или 0 — с помощью неё указывается, надо ли применять многопутевое слияние или нет.
