Алгоритм турнирной сортировки (Tournament Sort): принцип работы

Также упоминается как: Сортировка деревом выбора, Сортировка деревом победителей, Сортировка деревом турнира

Идея метода сортировки

Представьте сетку плей-офф (например, в теннисе). На нижнем уровне находятся участники (исходный массив). В каждом матче соревнуются два соседних участника, и победитель проходит в следующий раунд (поднимается на уровень выше). В нашем случае "победителем" объявляется наименьшее число, так как мы хотим отсортировать массив по возрастанию.

Алгоритм работает так:

• Шаг 1 (Построение турнира): Исходные элементы массива становятся листьями двоичного дерева (на нижнем уровне). Мы проводим матчи снизу вверх. В каждом родительском узле записываем минимум из двух его потомков. Корень дерева в итоге будет содержать абсолютный минимум всего массива.
• Шаг 2 (Извлечение победителя): Мы забираем значение из корня дерева и помещаем его в итоговый отсортированный массив.
• Шаг 3 (Переигровка): Мы спускаемся к тому листу, откуда пришел победитель, и заменяем его значение на ∞ (бесконечность). Затем мы проводим "переигровку" матчей только по пути от этого листа к корню дерева. Новый победитель окажется в корне.
• Шаг 4: Повторяем извлечение и переигровку, пока не извлечем все элементы.

В этом тренажере можно понаблюдать за турнирной сортировкой в деле: как строится дерево победителей и по одному выбираются минимумы.

Анализ алгоритма

Турнирная сортировка - это первая встретившаяся нам сортировка, преодолевающая квадратичный барьер O(N²).

Временная сложность:

• Построение первоначального дерева турнира требует N - 1 сравнений (где N - количество элементов). Это O(N).
• Извлечение корня и "переигровка" ветки до низа дерева требует столько сравнений, какова высота дерева. Так как дерево идеально сбалансировано, его высота равна log N.
• Мы делаем извлечение N раз, получая O(N log N).

Недостаток (Пространственная сложность):

Для проведения турнира нам нужно хранить структуру всего дерева. Для N листьев требуется N - 1 внутренних узлов. То есть нам требуется дополнительная память O(N). Именно из-за этих затрат памяти накладные расходы турнирной сортировки привели к тому, что на практике ее вытеснил ее "прямой потомок" - Пирамидальная сортировка (Heap Sort), которая умеет делать то же самое вообще без дополнительной памяти O(1).

Реализация на C

Так как размер дерева известен заранее, его удобно хранить в одномерном массиве размером 2 * N, где индексы с N по 2N - 1 - это листья (исходные элементы), а индексы от 1 до N - 1 - внутренние узлы-победители. Дети узла i находятся по индексам 2*i и 2*i + 1.

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

#define INF INT_MAX

// Турнирная сортировка
void TournamentSort(int arr[], int n) {
    // В дереве 2*n элементов (индекс 0 не используем для удобства умножения на 2)
    int tree_size = 2 * n;
    int* tree = (int*)malloc(tree_size * sizeof(int));
    // Хранит индекс откуда пришел победитель
    int* index_tree = (int*)malloc(tree_size * sizeof(int));

    // Шаг 1: Заполняем листья (от n до 2n-1)
    for (int i = 0; i < n; i++) {
        tree[n + i] = arr[i];
        index_tree[n + i] = n + i;
    }

    // Шаг 2: Проводим начальный турнир снизу вверх (от n-1 до 1)
    for (int i = n - 1; i > 0; i--) {
        int left = 2 * i;
        int right = 2 * i + 1;
        if (tree[left] < tree[right]) {
            tree[i] = tree[left];
            index_tree[i] = index_tree[left];
        } else {
            tree[i] = tree[right];
            index_tree[i] = index_tree[right];
        }
    }

    // Шаг 3: Извлекаем победителей
    for (int i = 0; i < n; i++) {
        // Корень дерева (индекс 1) всегда содержит текущий минимум
        arr[i] = tree[1];
        
        // Находим лист, из которого пришел этот минимум
        int leaf_idx = index_tree[1];
        
        // Заменяем его на бесконечность
        tree[leaf_idx] = INF;
        
        // Переигрываем матчи от листа к корню
        int current = leaf_idx / 2;
        while (current > 0) {
            int left = 2 * current;
            int right = 2 * current + 1;
            
            if (tree[left] < tree[right]) {
                tree[current] = tree[left];
                index_tree[current] = index_tree[left];
            } else {
                tree[current] = tree[right];
                index_tree[current] = index_tree[right];
            }
            current /= 2;
        }
    }

    free(tree);
    free(index_tree);
}