Skip to content

Tournament Sort

This page provides a brief introduction to tournament sort.

Definition

Tournament sort, also known as tree selection sort, is an optimized version of selection sort and a variant of heap sort (both using a complete binary tree). It improves upon selection sort by using a priority queue to find the next element to select.

Introduction

The name "tournament sort" comes from the single-elimination competition format. In such a format, many participants compete in pairwise matches, with winners advancing to the next round. This elimination method can determine the best participant, but the participant eliminated in the final round may not be the second-best—they might be inferior to some previously eliminated participants.

Process

Taking the minimum tournament sort tree as an example:

tournament-sort1

The elements to be sorted are those displayed at the leaf nodes. The red edges show the winning paths of the smaller elements in each round of comparison. Clearly, completing one "tournament" can select the smallest element from a group.

After each round of comparing \(n\) elements, \(\frac{n}{2}\) "winners" are obtained, with the smaller element from each pair advancing to the next round. If a pair cannot be formed, the element directly advances to the next round.

tournament-sort2

After completing one "tournament," the selected element must be removed. This is done by setting it to \(\infty\) (similar to heap sort), and then holding another "tournament" to select the next smallest element.

This process is repeated 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 complexities of tournament sort are all \(O(n\log n)\). It takes \(O(n)\) time to initialize the "tournament" and \(O(\log n)\) time to select one element from \(n\) elements.

Space Complexity

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

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
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 creat_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 recreat(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() {
  int value;
  creat_tree(value);
  for (int i = 0; i < n; i++) {
    a[i] = value;
    recreat(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
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 creat_tree():
    for i in range(0, n):
        tmp[n + i] = 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[1]]
    tmp[tmp[1]] = INF
    return value


def recreat():
    i = tmp[1]
    while i > 1:
        j = k = int(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():
    value = creat_tree()
    for i in range(0, n):
        a[i] = value
        value = recreat()
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用