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

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

Представьте, что мы сортируем дробные числа на математическом полуинтервале [0, 1) - то есть от 0.0 (включительно) до 1.0 (не включительно). У нас 100 чисел. Мы можем создать 10 "карманов" (массивов или связных списков): первый для чисел от 0.0 до 0.1, второй от 0.1 до 0.2 и так далее.

• Шаг 1 (Scatter): Проходим по всем элементам и вычисляем номер кармана для каждого из них (например, умножая число на 10 и округляя вниз). Кладем элемент в нужный карман.
• Шаг 2 (Sort): Сортируем элементы внутри каждого кармана. Так как элементов в каждом кармане ожидается немного (если данные равномерны), можно использовать простую Сортировку вставкой (Insertion Sort), которая очень быстра на малых массивах.
• Шаг 3 (Gather): Проходим по карманам по порядку (от нулевого до последнего) и выписываем все элементы в финальный массив.

В интерактивном блоке ниже видно, как карманная сортировка распределяет числа по карманам, наводит в них порядок и собирает все обратно.

Анализ сложности

В лучшем и среднем случае, когда данные распределены равномерно, в каждый из K карманов попадет примерно N/K элементов. Сортировка малого количества элементов займет константное время O(1) для каждого кармана. Общее время составит O(N + K).

Однако, если мы отсортируем массив, в котором 99% чисел лежат в узком диапазоне (например, от 0.5 до 0.51), почти все они попадут в один карман. Тогда мы будем вынуждены применять Сортировку вставкой к массиву длины N, что даст худшее время O(N²).

Варианты и оптимизации

Базовая концепция распределения по карманам породила несколько интересных алгоритмов-наследников:

• Proxmap Sort: Использует специальную функцию (похожую на хеширование), которая вычисляет почти точную финальную позицию каждого элемента. Если данные распределены хорошо, сортировка внутри карманов почти не требуется, так как элементы сразу попадают на нужные места.
• Histogram Sort (Интерполяционная сортировка): Делает предварительный проход по массиву, чтобы подсчитать количество элементов для каждого кармана (строит гистограмму). Это позволяет заранее выделить массивы точного размера и гарантировать более равномерное распределение, снижая риск деградации до O(N²).
• Postman's Sort (Сортировка почтальона): Иерархический вариант, вдохновленный сортировкой писем (сначала по регионам, затем по городам, улицам и т.д.). Применяется как многопроходная сортировка для сложных ключей (очень похожа на MSD Radix Sort), где на каждом шаге элементы распределяются по карманам в зависимости от очередного атрибута.
• Shuffle Sort: Редкий термин, которым иногда обозначают гибридные подходы к распределяющей сортировке с перетасовкой элементов по буферам. (Примечание: не путайте с Cocktail Shaker Sort - двунаправленной пузырьковой сортировкой).

Реализация на C (для чисел с плавающей точкой)

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

// Узел для связного списка (кармана)
struct Node {
    float data;
    struct Node* next;
};

// Функция вставки в сортированный связный список (Сортировка вставкой)
void InsertSorted(struct Node** head, float val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = val;
    
    if (*head == NULL || (*head)->data >= val) {
        newNode->next = *head;
        *head = newNode;
    } else {
        struct Node* current = *head;
        while (current->next != NULL && current->next->data < val) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

// Карманная сортировка
void BucketSort(float arr[], int n) {
    // Создаем N карманов
    struct Node** buckets = (struct Node**)calloc(n, sizeof(struct Node*));
    
    // Шаг 1: Раскладываем элементы по карманам
    // Формула: индекс = n * arr[i] (для чисел в диапазоне [0.0, 1.0))
    for (int i = 0; i < n; i++) {
        int bucketIndex = n * arr[i];
        // Сразу вставляем элемент в карман в отсортированном порядке
        InsertSorted(&buckets[bucketIndex], arr[i]);
    }
    
    // Шаг 3: Собираем элементы обратно
    int index = 0;
    for (int i = 0; i < n; i++) {
        struct Node* current = buckets[i];
        while (current != NULL) {
            arr[index++] = current->data;
            struct Node* temp = current;
            current = current->next;
            free(temp); // Очищаем память
        }
    }
    free(buckets);
}