AIOJ

This page briefly introduces tournament sort.

Definition

Tournament sort (English: Tournament sort), also known as tree selection sort, is an optimized version of selection sort and a variant of heap sort (both use complete binary trees). On the basis of selection sort, it uses a priority queue to find the next element to select.

Introduction

The name tournament sort comes from the single-elimination tournament format. In this format, many contestants participate; they compete in pairs, and the winner advances to the next round. This elimination method can determine the best contestant, but the contestant eliminated in the final round is not necessarily the second-best—they may be worse than a contestant eliminated earlier.

Process

Take a minimum tournament sort tree as an example:

tournament-sort1

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

After comparing $n$ elements in each round, $\frac{n}{2}$ “winners” can be obtained; the smaller element in each pair advances to the next comparison round. If a pair cannot be formed, that element directly advances to the next comparison round.

tournament-sort2

After completing a “tournament”, remove the selected element. Set it directly to $\infty$ (this operation is similar to heap sort), and then hold another “tournament” to select the next-smallest element.

Repeat this operation 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 complexities of tournament sort are all $O(n\log n)$ . It initializes the “tournament” in $O(n)$ time, and selects one element from $n$ elements in $O(\log n)$ time.

Space Complexity

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

Implementation

C++

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);
  }
}

Python

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()

External Links

Tournament sort - Wikipedia

Tournament Sort