Как стать автором
Обновить
85.94
Рейтинг
Edison
Изобретаем успех: софт и стартапы

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

Блог компании Edison Ruby *Программирование *Алгоритмы *

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


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

Мы очень любим computer science ;-)
Основная идея Tournament sort заключается в использовании относительно небольшой (по сравнению с основным массивом) вспомогательной кучи, которая выполняет роль приоритетной очереди. В этой куче сравниваются элементы на нижних уровнях, в результате чего меньшие элементы (в данном случае дерево у нас 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 log2 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 — с помощью неё указывается, надо ли применять многопутевое слияние или нет.
Теги:
Хабы:
Всего голосов 12: ↑11 и ↓1 +10
Просмотры 5.3K
Комментарии Комментировать

Информация

Дата основания
Местоположение
Россия
Сайт
www.edsd.ru
Численность
31–50 человек
Дата регистрации