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

Также упоминается как: Цифровая сортировка, Сортировка по основанию

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

Чаще всего используют метод LSD (Least Significant Digit) - сортировку, начиная с самого младшего разряда (справа налево). Этот алгоритм опирается на важное свойство: промежуточная сортировка по каждому разряду обязана быть устойчивой (stable).

Почему важна устойчивость? Если мы сначала отсортировали числа по единицам, а затем сортируем по десяткам, алгоритм сортировки десятков не должен перепутать порядок чисел с одинаковыми десятками! Например, числа 21 и 25 после шага единиц стоят как 21, 25. На шаге десятков они попадают в одну корзину "2". Если промежуточная сортировка устойчива, их взаимный порядок сохранится, и они так и останутся 21, 25.

• В качестве промежуточной устойчивой сортировки обычно используют модифицированную сортировку подсчетом (Counting Sort).
• Мы делаем D проходов сортировки подсчетом, где D - количество цифр в самом длинном числе.

Тренажер позволяет в деталях рассмотреть поразрядную сортировку: как числа группируются сначала по младшим цифрам, а затем по старшим.

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

Каждый вызов сортировки подсчетом требует времени O(N + K), где K=10 (цифры от 0 до 9). Мы делаем этот вызов D раз. Итоговое время: O(D * (N + K)).

Может показаться, что это чистая O(N). Но вспомните: если максимальное число равно M, то количество цифр D в нем примерно равно log_10(M). Таким образом, истинная сложность зависит от величины чисел. Если мы сортируем очень большие числа, алгоритм может проиграть той же сортировке Хоара из-за накладных расходов на создание очередей и копирование массивов.

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

// Функция для получения максимума (чтобы узнать число разрядов)
int GetMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
    return max;
}

// Устойчивая сортировка подсчетом для конкретного разряда (exp = 1, 10, 100...)
void CountingSortByDigit(int arr[], int n, int exp) {
    int* output = (int*)malloc(n * sizeof(int)); // Временный массив
    int count[10] = {0}; // Очереди для цифр от 0 до 9

    // Считаем частоту каждой цифры в заданном разряде
    for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;

    // Считаем префиксные суммы (для обеспечения устойчивости алгоритма)
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];

    // Восстанавливаем элементы во временный массив (ИДЕМ С КОНЦА ДЛЯ УСТОЙЧИВОСТИ)
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // Копируем обратно
    for (int i = 0; i < n; i++) arr[i] = output[i];
    free(output);
}

// Главная функция поразрядной сортировки
void RadixSort(int arr[], int n) {
    int max = GetMax(arr, n);
    // Проходим по каждому разряду (exp умножается на 10 на каждом шаге)
    for (int exp = 1; max / exp > 0; exp *= 10) {
        CountingSortByDigit(arr, n, exp);
    }
}