Tournament Sort

Last translate with upstream: 08eb0c5 #3333 on Jul 17, 2021.

This article will briefly introduce the tournament sort.

Introduction

Tournament sort is a optimization for naive selection sort, and a variation of heapsort (with complete ). It performs based by selection sort by using a priority queue to find next element to select.

The algorithm is named after a single-elimination tournament, where there are many players (or teams) that play in two-sided matches. Each match compares the players and the winner is promoted to next round. The tournament determines the best player, but the player who was beaten in the final match may not be the second best – he may be inferior to other players the winner beated.1

Principles

Here is an example of minimum tournament tree:

tournament-sort1

The leaf nodes represent unordered elements. The red edges represent winner path of each round. Obviously, finishing a tournament can find out the minimum element from a group of elements.

After each round of comparison among n elements, we will have \frac{n}{2} "winners". The smaller one from each pair of elements will enter next round of comparison. If no pair could be made, this element will directly enter next round.

tournament-sort2

After one "tournament" we need to eliminate the winner element by setting it to \infty (which is similar to heapsort and hold the "tournament" again to select secondly small element.

The repeat these operations until all elements are ordered.

Properties

Stability

Tournament sort is an unstable sorting algorithm.

Time Complexity

The best-case, average-case and worst-case time complexity of a tournament sort are all O(n\log n) . It uses a time complexity of O(n) to initialize a "tournament", and O(\log n) to select a minimum element from n elements.

Space Complexity

The space complexity of a tournament sort is O(n) .

Code Implementations

C++

// C++ Version
int n, a[maxn], tmp[maxn << 1];

int winner(int pos1, int pos2) {
  int u = pos1 >= n ? pos1 : tmp[pos1];
  int v = pos2 >= n ? pos2 : tmp[pos2];
  if (tmp[u] <= tmp[v]) return u;
  return v;
}

void create_tree(int &value) {
  for (int i = 0; i < n; i++) tmp[n + i] = a[i];
  for (int i = 2 * n - 1; i > 1; i -= 2) {
    int k = i / 2;
    int j = i - 1;
    tmp[k] = winner(i, j);
  }
  value = tmp[tmp[1]];
  tmp[tmp[1]] = INF;
}

void recreate(int &value) {
  int i = tmp[1];
  while (i > 1) {
    int j, k = i / 2;
    if (i % 2 == 0 && i < 2 * n - 1)
      j = i + 1;
    else
      j = i - 1;
    tmp[k] = winner(i, j);
    i = k;
  }
  value = tmp[tmp[1]];
  tmp[tmp[1]] = INF;
}

void tournament_sort() {
  int value;
  create_tree(value);
  for (int i = 0; i < n; i++) {
    a[i] = value;
    recreate(value);
  }
}

Python

# Python Version
n = 0
a = [0] * maxn
tmp = [0] * maxn * 2

def winner(pos1, pos2):
    u = pos1 if pos1 >= n else tmp[pos1]
    v = pos2 if pos2 >= n else tmp[pos2]
    if tmp[u] <= tmp[v]:
        return u
    return v

def create_tree(value):
    for i in range(0, n):
        tmp[n + 1] = a[i]
    for i in range(2 * n -1, 1, -2):
        k = int(i / 2)
        j = i - 1
        tmp[k] = winner(i, j)
    value = tmp[tmp[i]]
    tmp[tmp[i]] = INF

def recreate(value):
    i = tmp[1]
    while i > 1:
        j = k = int(i / 2)
        if i % 2 == 0 and i < 2 * n - 1:
            j = i + 1
        else:
            j = i - 1
        tmp[k] = winner(i, j)
        i = k
    value = tmp[tmp[1]]
    tmp[tmp[1]] = INF

def tournament_sort():
    value = 0
    create_tree(value)
    for i in range(0, n):
        a[i] = value
        recreate(value)

References and Footnotes

  1. Tournament sort - Wikipedia (Chapter "Etymology") ↩

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments