ITKarma picture

We continue to get acquainted with a variety of heaps and sorting algorithms using these heaps. Today we have the so-called tournament tree.
EDISON Software - web-development
At EDISON, we often develop smart algorithms in our projects.

ITKarma picture
For example, for one customer, a special method of transmitting data using the LED was developed. Initially, the customer planned to search and analyze a specific light spot in the video stream, but we proposed a more elegant and reliable solution.

We love computer science ;-)
ITKarma picture
The main idea of ​​Tournament sort is to use a relatively small (compared to the main array) auxiliary heap, which acts as a priority queue. In this heap, the elements at the lower levels are compared, as a result of which the smaller elements (in this case, the MIN-HEAP tree) go up, and the current minimum of the portion of the array elements that fall into this heap pops up to the root. The minimum is transferred to an additional array of "winners", as a result of which the heap compares/moves the remaining elements - and now a new minimum is in the root of the tree. Note that with such a system, the next minimum is greater in value than the previous one - then a new ordered array of “winners” is easily assembled, where new minimums are simply added to the end of the additional array.

Transferring the minima to the additional array leads to the appearance of vacant places for the following elements of the main array in the heap - as a result, all elements are processed in the order of the queue.

The main subtlety is that in addition to the “winners” there are also “losers”. If some elements have already been transferred to the “winners” array, then if the unprocessed elements are smaller than these “winners”, then there is no sense in sifting them through the tournament tree at this stage - inserting these elements into the “winners” array will be too expensive (in you can’t put an end to them already, but to put them at the beginning, you have to shift the already inserted lows). Such elements that did not manage to fit into the array of “winners” are sent to the array of “losers” - they will go through the tournament tree in one of the following iterations, when all actions are repeated for the remaining losers.

It’s not easy to find an implementation of this algorithm on the Internet, but on YouTube a clear and pretty implementation on Ruby was found. Java is still mentioned in the Links section, but it doesn't look so readable there.

# Библиотека для работы с приоритетной очередью в виде кучи 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 

This is a naive implementation, in which, after each division into “losers” and “winners”, these arrays are combined and then for the combined array all actions are repeated again. If the “losing” elements will go first in the combined array, then the sifting through the tournament pile will sort them together with the “winners”.

ITKarma picture

This implementation is quite simple and obvious, but you will not name it effective. Sorted "winners" go through the tournament tree more than once, which seems obviously unnecessary. I assume that the time complexity here is log-quadratic, O ( n log 2 n ) .

Multipath merge option


The algorithm is noticeably accelerated if the ordered elements passing through the sieve are not passed through tournament races repeatedly.

After the unordered array is divided into sorted “winners” and unsorted “losers”, the whole process is repeated anew only for “losers”. At each new iteration, a set of arrays with “winners” will accumulate and will continue this way until there are no “losers” at any step. After that, it remains only to merge all the arrays of "winners". Since all of these arrays are sorted, this merge takes place at minimal cost.

ITKarma picture

In this form, the algorithm may already find a useful application. For example, if you have to work with big data, then along the process of using the tournament heap, packets of ordered data will be released with which you can already do something while everything else is being processed.

Each of the n elements of the array passes through the tournament tree only once, which costs O (log n ) in time. In such an implementation, the algorithm has worse/average time complexity O ( n log n ) .

In the season finale


A series of articles on heap sorting is almost complete. It remains to talk about the most effective of them.

Links


ITKarma pictureTournament sort

ITKarma picturePriority queue

ITKarma pictureTournament sort in Java

ITKarma pictureThe Theory Behind the The Theory Behind the z/Architecture Sort Assist Instructions

ITKarma pictureUsing Tournament Trees to Sort

ITKarma pictureTournament Sort Demo Ruby

ITKarma pictureTournament Sort Visualization

ITKarma pictureTournament Sort Data Structure UGC NET DS

ITKarma pictureTournament Sort Algorithm - a Heapsort variant

Series Articles:



ITKarma picture
Today’s sorting has been added to the AlgoLab application, who is using it - update the excel file with macros.

In the comments to the cell with the name of the sort, you can specify some settings.
Variable way - how many-way tournament tree (just in case, it is possible to make this tree not only binary, but also ternary, quaternary and pentameric).
The variable queue is the size of the initial queue (the number of nodes at the lowest level of the tree). Since the trees are full, if, for example, with way=2, specify queue=5, then the queue size will be increased to the nearest power of two (in this case, to 8).
The variable NWayMerge takes the value 1 or 0 - with the help of it it is indicated whether to use multi-path merging or not.

Source