Турнирная сортировка

Продолжаем знакомиться с разнообразными кучами и алгоритмами сортировок с помощью этих куч. Сегодня у нас так называемое турнирное дерево.

Мы в EDISON часто разрабатываем умные алгоритмы в наших проектах.

Например, для одного заказчика был разработан специальный способ передачи данных с помощью светодиода. Изначально заказчик планировал поиск и анализ конкретного светового пятная в видеопотоке, однако мы предложили более элегантное и надёжное решение.

Мы очень любим computer science ;-)

Основная идея заключается в использовании относительно небольшой (по сравнению с основным массивом) вспомогательной кучи, которая выполняет роль приоритетной очереди. В этой куче сравниваются элементы на нижних уровнях, в результате чего меньшие элементы (в данном случае дерево у нас MIN-HEAP) поднимаются наверх, а в корень всплывает текущий минимум из той порции элементов массива, которые попали в эту кучу. Минимум переносится в дополнительный массив «победителей», в результате чего в куче происходит сравнение/перемещение оставшихся элементов — и вот уже в корне дерева новый минимум. Отметим, что при такой системе очередной минимум по значению больше чем предыдущий — тогда легко собирается новый упорядоченный массив «победителей», где новые минимумы просто добавляются в конец дополнительного массива.

Перенос минимумов в дополнительный массив приводит к тому, что в куче появляются вакантные места для следующих элементов основного массива — в результате чего в порядке очереди обрабатываются все элементы.

Главной тонкостью является то, что кроме «победителей» есть ещё и «проигравшие». Если в массив «победителей» уже перенесены какие-то элементы, то если необработанные элементы меньше, чем эти «победители» то просеивать их через турнирное дерево на этом этапе уже нет смысла — вставка этих элементов в массив «победителей» будет слишком дорогой (в конец их уже не поставишь, а чтобы поставить в начало — придётся сдвинуть уже вставленные раннее минимумы). Такие элементы, не успевшие вписаться в массив «победителей» отправляются в массив «проигравших» — они пройдут через турнирное дерево в одной из следующих итерации, когда все действия повторяются для оставшихся неудачников.

В Интернете непросто найти реализацию этого алгоритма, однако в Ютубе обнаружилась понятная и симпатичная реализация на Руби. В разделе «Ссылки» ещё упомянут код на 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

Это наивная реализация, в которой после каждого разделения на «проигравших» и «победителей» эти массивы объединяются и затем для объединённого массива все действия повторяются снова. Если в объединённом массиве будут сначала идти «проигравшие» элементы, то просейка через турнирную кучу упорядочит их совместно с «победителями».

Данная реализация достаточно проста и наглядна, но эффективной её не назовёшь. Отсортированные «победители» проходят через турнирное дерево неоднократно, что выглядит, очевидно, излишним. Предполагаю, что временна́я сложность здесь логарифмично-квадратичная, O(n log² n).

Вариант с многопутевым слиянием

Алгоритм заметно ускоряется, если прошедшие через сито упорядоченные элементы не пропускать через турнирные забеги повторно.

После того как неупорядоченный массив разделится на отсортированных «победителей» и неотсортированных «проигравших», весь процесс заново повторяем только для «проигравших». На каждой новой итерации будет накапливаться набор массивов с «победителями» и так будет продолжаться до тех пор, пока на каком то шаге «проигравших» уже не останется. После чего останется только произвести слияние всех массивов «победителей». Так как все эти массивы отсортированы, это слияние проходит с минимальными затратами.

В таком виде алгоритм может уже вполне найти полезное применение. Например, если приходится работать с big data, то по ходу процесса с помощью турнирной кучи будут выходить пакеты упорядоченных данных, с которыми уже можно что-нибудь делать, пока обрабатывается и всё остальное.

Каждый из n элементов массива проходит через турнирное дерево всего один раз, что обходится в O(log n) по времени. В такой реализации алгоритм имеет худшую/среднюю временну́ю сложность O(n log 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

Статьи серии:

В приложение AlgoLab добавлена сегодняшняя сортировка, кто пользуется — обновите excel-файл с макросами.

В комментариях к ячейке с название сортировки можно указать некоторые настройки.
Переменная way — скольки-путевое турнирное дерево (просто на всякий случай предусмотрена возможность делать это дерево не только двоичным, но и троичным, четверичным и пятиричным).
Переменная queue — это размер первоначальной очереди (количество узлов в самом нижнем уровне дерева). Так как деревья полные, то если, к примеру при way=2 указать queue=5, то размер очереди будет увеличен до ближайшей степени двойки (в данном случае до 8).
Переменная NWayMerge принимает значение 1 или 0 — с помощью неё указывается, надо ли применять многопутевое слияние или нет.

Let's block ads! (Why?)