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


    Продолжаем знакомиться с разнообразными кучами и алгоритмами сортировок с помощью этих куч. Сегодня у нас так называемое турнирное дерево.
    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 — с помощью неё указывается, надо ли применять многопутевое слияние или нет.
    Edison
    Изобретаем успех: софт и стартапы

    Comments 0

    Only users with full accounts can post comments. Log in, please.