Skip to content

Tournament Sort

This page gives a brief introduction to tournament sort.

Definition

Tournament sort, also known as tree selection sort, is an improved version of selection sort and a variant of heapsort (both use a complete binary tree). It is selection sort that uses a priority queue to find the next element to select.

Introduction

Tournament sort is named after the single-elimination tournament. In this contest format many contestants take part; they are compared in pairs, and the winner of each pair advances to the next round. Elimination of this kind determines the best contestant, but the contestant knocked out in the final round is not necessarily the second best: he may be worse than a contestant knocked out earlier.

Procedure

Take a min tournament tree as the example:

tournament-sort1

The leaves show the elements to be sorted. The red edges show the path along which the smaller element of each round of comparisons advances. Clearly, one tournament selects the smallest element of a set.

A round of comparisons among \(n\) elements produces \(\left\lceil\dfrac{n}{2}\right\rceil\) winners: the smaller element of each pair goes on to the next round. An element that cannot be paired up goes straight to the next round.

tournament-sort2

After a tournament, the selected element has to be removed. Simply set it to \(\infty\) (much as in heapsort) and hold another tournament to select the second smallest element.

Repeat this until all elements are sorted.

Properties

Stability

Tournament sort is an unstable sorting algorithm.

Time complexity

The best-case, average-case and worst-case time complexity of tournament sort are all \(O(n\log n)\). It takes \(O(n)\) time to set up the tournament and then \(O(\log n)\) time to select one element out of the \(n\) elements.

Space complexity

Tournament sort uses \(O(n)\) space.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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)
      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() {
  if (n <= 1) return;
  int value;
  create_tree(value);
  for (int i = 0; i < n; i++) {
    a[i] = value;
    recreate(value);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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():
    for i in range(0, n):
        tmp[n + i] = a[i]
    for i in range(2 * n - 1, 1, -2):
        k = i // 2
        j = i - 1
        tmp[k] = winner(i, j)
    value = tmp[tmp[1]]
    tmp[tmp[1]] = INF
    return value


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


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