Блочная сортировка: интерактивная анимация (Bucket Sort)

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

// Простая структура для элемента односвязного списка (наша корзина)
struct Node {
    int data;          // Значение элемента
    struct Node* next; // Указатель на следующий элемент списка
};

// Функция для вставки элемента в отсортированный связный список (сортировка вставками)
void insert_sorted(struct Node** head_ref, int new_data) {
    // Выделяем память под новый узел
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    struct Node* current;

    // Если список пуст или новый элемент меньше головы списка
    if (*head_ref == NULL || (*head_ref)->data >= new_node->data) {
        new_node->next = *head_ref;
        *head_ref = new_node; // Новый узел становится новой головой
    } else {
        current = *head_ref;
        // Ищем узел, после которого нужно вставить новый элемент
        while (current->next != NULL && current->next->data < new_node->data) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node; // Вставляем элемент на правильную позицию
    }
}

// Основная функция блочной сортировки
void bucket_sort(int arr[], int n) {
    const int NUM_BUCKETS = 5;  // Количество корзин
    const int BUCKET_SIZE = 20; // Размер диапазона одной корзины
    
    // Создаем массив указателей на головы списков (корзины) и инициализируем нулями
    struct Node** buckets = (struct Node**)calloc(NUM_BUCKETS, sizeof(struct Node*));

    // Шаг 1. Раскладываем элементы исходного массива по корзинам
    // Сразу вставляем их так, чтобы внутри корзины сохранялся порядок (сортировка вставками)
    for (int i = 0; i < n; i++) {
        int idx = (arr[i] - 1) / BUCKET_SIZE; // Вычисляем индекс корзины для элемента
        if (idx >= NUM_BUCKETS) idx = NUM_BUCKETS - 1; // Защита от выхода за границы
        insert_sorted(&buckets[idx], arr[i]);
    }

    // Шаг 2. Собираем элементы обратно в исходный массив
    int index = 0;
    for (int i = 0; i < NUM_BUCKETS; i++) {
        struct Node* current = buckets[i];
        // Проходим по каждому элементу в текущей корзине
        while (current != NULL) {
            arr[index++] = current->data; // Записываем значение обратно в массив
            struct Node* temp = current;
            current = current->next; // Переходим к следующему элементу списка
            free(temp); // Освобождаем память, выделенную под узел
        }
    }
    // Освобождаем массив указателей на корзины
    free(buckets);
}

def bucket_sort(arr):
    # Если массив пуст, сортировать нечего
    if len(arr) == 0:
        return arr
        
    num_buckets = 5  # Количество корзин
    bucket_size = 20 # Размер диапазона каждой корзины
    # Создаем пустые корзины (списки внутри списка)
    buckets = [[] for _ in range(num_buckets)]

    # Шаг 1. Раздаем элементы по корзинам
    for num in arr:
        # Вычисляем индекс корзины на основе значения элемента
        idx = (num - 1) // bucket_size
        if idx >= num_buckets:
            idx = num_buckets - 1 # Все большие значения падают в последнюю корзину
        buckets[idx].append(num)

    # Шаг 2. Сортируем элементы внутри каждой корзины
    for i in range(num_buckets):
        # Используем встроенную сортировку Python (Timsort),
        # но в классическом алгоритме здесь обычно пишут сортировку вставками
        buckets[i].sort()

    # Шаг 3. Склеиваем отсортированные корзины в единый результат
    k = 0
    for i in range(num_buckets):
        for j in range(len(buckets[i])):
            arr[k] = buckets[i][j] # Перезаписываем элементы в исходный массив
            k += 1

    return arr

function bucketSort(arr) {
    // Базовый случай: пустой массив уже отсортирован
    if (arr.length === 0) return arr;
    
    const numBuckets = 5;  // Общее количество корзин
    const bucketSize = 20; // Диапазон значений, за который отвечает корзина
    // Инициализируем массив пустых массивов (наши корзины)
    const buckets = Array.from({ length: numBuckets }, () => []);

    // Шаг 1. Распределяем каждый элемент по своей корзине
    for (let i = 0; i < arr.length; i++) {
        // Вычисляем индекс корзины (считая, что минимальное значение массива ~ 1)
        let idx = Math.floor((arr[i] - 1) / bucketSize);
        if (idx >= numBuckets) idx = numBuckets - 1; // Ограничение по максимальному индексу
        buckets[idx].push(arr[i]);
    }

    // Шаг 2. Сортируем каждую корзину отдельно (используем сортировку вставками)
    for (let i = 0; i < numBuckets; i++) {
        let bucket = buckets[i];
        // Классическая сортировка вставками для текущей корзины
        for (let j = 1; j < bucket.length; j++) {
            let key = bucket[j];
            let k = j - 1;
            // Сдвигаем элементы, пока не найдем подходящее место для key
            while (k >= 0 && bucket[k] > key) {
                bucket[k + 1] = bucket[k];
                k--;
            }
            bucket[k + 1] = key; // Вставляем элемент на нужную позицию
        }
    }

    // Шаг 3. Собираем отсортированные данные обратно в исходный массив
    let index = 0;
    for (let i = 0; i < numBuckets; i++) {
        // Так как корзины упорядочены по диапазонам, и внутри тоже отсортированы,
        // просто переписываем элементы по порядку
        for (let j = 0; j < buckets[i].length; j++) {
            arr[index++] = buckets[i][j];
        }
    }

    return arr;
}