Турнирная сортировка: интерактивная анимация (Tournament Sort)

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

// Турнирная сортировка (Tournament Sort)
// Время: O(n log n), Память: O(n) (для дерева турнира)
// Идея: строим турнирную сетку (дерево) победителей, где каждый узел - минимум из детей.
// Победитель (минимальный элемент) оказывается в корне.
// Затем мы извлекаем корень, а его место в листьях заменяем на "бесконечность" и переигрываем.

// Находим ближайшую степень двойки (нужно для листьев полного бинарного дерева)
int nextPow2(int n) {
    int p = 1;
    while (p < n) p *= 2;
    return p;
}

void tournamentSort(int arr[], int n) {
    if (n <= 1) return;

    // Количество листьев в полном двоичном дереве
    int leafCount = nextPow2(n);
    // Всего узлов в дереве = 2 * leafCount - 1
    int totalNodes = 2 * leafCount - 1;
    // Индекс первого листа в массиве дерева
    int firstLeaf = leafCount - 1;
    
    // Выделяем память под турнирное дерево. 
    // ВАЖНО: tree[i] будет хранить не сами значения, а ИНДЕКСЫ исходных элементов в массиве arr.
    // Это позволяет легко понять, кто откуда пришел.
    int* tree = (int*)malloc(totalNodes * sizeof(int));
    
    // 1. Инициализация листьев дерева
    for (int i = 0; i < leafCount; i++) {
        if (i < n) 
            tree[firstLeaf + i] = i;  // Реальный элемент
        else 
            tree[firstLeaf + i] = -1; // Пустышка (для неполных деревьев)
    }
    
    // Макрос-помощник: если индекс -1, возвращаем бесконечность (INT_MAX)
    #define VAL(origIdx) (origIdx == -1 ? INT_MAX : arr[origIdx])
    
    // 2. Первичное построение дерева (снизу вверх)
    for (int i = firstLeaf - 1; i >= 0; i--) {
        int leftVal = VAL(tree[2 * i + 1]);
        int rightVal = VAL(tree[2 * i + 2]);
        
        // При равенстве значений всегда побеждает левый потомок.
        // Это гарантирует устойчивость сортировки (стабильность)!
        tree[i] = (leftVal <= rightVal) ? tree[2 * i + 1] : tree[2 * i + 2];
    }
    
    // Массив для постепенного сбора отсортированного результата
    int* output = (int*)malloc(n * sizeof(int));
    
    // 3. Извлечение элементов по одному (всегда берем чемпиона из корня)
    for (int extract = 0; extract < n; extract++) {
        // Чемпион турнира всегда в tree[0]
        int champOrigIdx = tree[0];
        output[extract] = arr[champOrigIdx];
        
        // Находим лист, из которого пришел чемпион
        int champLeaf = firstLeaf + champOrigIdx;
        
        // Помечаем этот лист как "выбывший" (заменяем на пустышку)
        tree[champLeaf] = -1;
        
        // 4. Переигрываем матчи только по пути от листа чемпиона к корню (O(log n) операций)
        int cur = champLeaf;
        while (cur > 0) {
            cur = (cur - 1) / 2; // Переходим к родителю
            int leftVal = VAL(tree[2 * cur + 1]);
            int rightVal = VAL(tree[2 * cur + 2]);
            // Снова разыгрываем матч на этом уровне
            tree[cur] = (leftVal <= rightVal) ? tree[2 * cur + 1] : tree[2 * cur + 2];
        }
    }
    
    // 5. Копируем отсортированный результат обратно в оригинальный массив
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    
    // Освобождаем выделенную память
    free(tree);
    free(output);
}

import math

# Турнирная сортировка (Tournament Sort)
# Оптимизирована для поиска минимумов через построение дерева "матчей".
# Сложность: O(n log n) время, O(n) память.
def tournament_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
        
    # Дополняем количество листьев до ближайшей степени двойки,
    # чтобы получилось идеальное полное бинарное дерево.
    leaf_count = 2 ** math.ceil(math.log2(n))
    total_nodes = 2 * leaf_count - 1
    first_leaf = leaf_count - 1
    
    # Дерево будет хранить индексы элементов массива arr, а не сами значения.
    # -1 означает пустое место ("выбывший" участник турнира).
    tree = [-1] * total_nodes
    
    # 1. Раскладываем элементы по листьям
    for i in range(leaf_count):
        if i < n:
            tree[first_leaf + i] = i
            
    # Вспомогательная функция для получения значения (если -1, то это бесконечность)
    def get_val(orig_idx):
        return float('inf') if orig_idx == -1 else arr[orig_idx]
        
    # 2. Проводим начальный турнир: от листьев к корню
    for i in range(first_leaf - 1, -1, -1):
        left_val = get_val(tree[2 * i + 1])
        right_val = get_val(tree[2 * i + 2])
        # При равенстве (<=) побеждает левый элемент - это сохраняет устойчивость сортировки
        tree[i] = tree[2 * i + 1] if left_val <= right_val else tree[2 * i + 2]
        
    output = []
    
    # 3. Извлекаем победителей по одному
    for _ in range(n):
        # Корень дерева (tree[0]) всегда содержит индекс минимального элемента
        champ_idx = tree[0]
        output.append(arr[champ_idx])
        
        # Находим позицию чемпиона в листьях и "удаляем" его из турнира
        champ_leaf = first_leaf + champ_idx
        tree[champ_leaf] = -1
        
        # 4. Переигрываем матчи только по ветке чемпиона снизу вверх
        # Это занимает O(log n) шагов
        cur = champ_leaf
        while cur > 0:
            cur = (cur - 1) // 2
            left_val = get_val(tree[2 * cur + 1])
            right_val = get_val(tree[2 * cur + 2])
            tree[cur] = tree[2 * cur + 1] if left_val <= right_val else tree[2 * cur + 2]
            
    # Записываем результат обратно в массив (или возвращаем output)
    for i in range(n):
        arr[i] = output[i]
        
    return arr

/**
 * Турнирная сортировка (Tournament Sort)
 * 
 * Построение турнирной сетки дает нам логарифмическое время O(log n)
 * на поиск каждого следующего минимального элемента. 
 * В отличие от Heap Sort, требует O(n) дополнительной памяти.
 */
function tournamentSort(arr) {
    let n = arr.length;
    if (n <= 1) return arr;

    // Вычисляем ближайшую степень двойки для листьев турнирного дерева
    let leafCount = 1;
    while (leafCount < n) leafCount *= 2;
    
    let totalNodes = 2 * leafCount - 1;
    let firstLeaf = leafCount - 1;
    
    // В дереве храним оригинальные индексы. -1 обозначает бесконечность (отсутствие участника).
    let tree = new Array(totalNodes).fill(-1);
    
    // 1. Инициализация листьев дерева исходными индексами
    for (let i = 0; i < leafCount; i++) {
        if (i < n) tree[firstLeaf + i] = i;
    }
    
    // Функция-хелпер: возвращает значение элемента или Infinity для выбывших (-1)
    const getVal = (origIdx) => (origIdx === -1 ? Infinity : arr[origIdx]);
    
    // 2. Первоначальное построение турнирной сетки (снизу вверх)
    for (let i = firstLeaf - 1; i >= 0; i--) {
        let leftVal = getVal(tree[2 * i + 1]);
        let rightVal = getVal(tree[2 * i + 2]);
        
        // Устойчивость: если элементы равны, левый проходит дальше
        tree[i] = (leftVal <= rightVal) ? tree[2 * i + 1] : tree[2 * i + 2];
    }
    
    let output = [];
    
    // 3. Вытягивание элементов по одному из корня
    for (let k = 0; k < n; k++) {
        // Абсолютный минимум всего оставшегося массива лежит в корне
        let champIdx = tree[0];
        output.push(arr[champIdx]);
        
        // Лист, откуда пришел чемпион, "сгорает" (заменяется на -1)
        let champLeaf = firstLeaf + champIdx;
        tree[champLeaf] = -1;
        
        // 4. Переигрываем матчи для нового чемпиона по одной ветке
        // Мы поднимаемся от пустого листа до корня и обновляем победителей (O(log n) шагов)
        let cur = champLeaf;
        while (cur > 0) {
            cur = Math.floor((cur - 1) / 2);
            let leftVal = getVal(tree[2 * cur + 1]);
            let rightVal = getVal(tree[2 * cur + 2]);
            tree[cur] = (leftVal <= rightVal) ? tree[2 * cur + 1] : tree[2 * cur + 2];
        }
    }
    
    // 5. Заливка отсортированных данных обратно в исходный массив
    for (let i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    
    return arr;
}