«1. Введение

В этом уроке мы узнаем о сортировке по основанию, проанализируем ее производительность и рассмотрим ее реализацию.

Здесь мы сосредоточимся на использовании Radix Sort для сортировки целых чисел, но это не ограничивается только числами. Мы также можем использовать его для сортировки других типов, таких как String.

Для простоты мы сосредоточимся на десятичной системе, в которой числа выражаются по основанию (основанию) 10.

2. Обзор алгоритма

Сортировка по основанию — это алгоритм сортировки, который сортирует числа в зависимости от положения их цифр. По сути, он использует разрядное значение цифр в числе. В отличие от большинства других алгоритмов сортировки, таких как сортировка слиянием, сортировка вставками, пузырьковая сортировка, он не сравнивает числа.

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

Поразрядная сортировка работает путем сортировки цифр от младшей значащей цифры (LSD) до самой старшей значащей цифры (MSD). Мы также можем реализовать сортировку по основанию для обработки цифр из MSD.

3. Краткий пример

Давайте посмотрим, как это работает на примере. Рассмотрим следующий массив:

Итерация 1:

Мы отсортируем этот массив, обрабатывая цифры из LSD и двигаясь к MSD.

Итак, начнем с разряда единиц:

После первой итерации массив теперь выглядит так:

Обратите внимание, что числа отсортированы по разряду разрядов.

Итерация 2:

Перейдем к разряду десятков:

Теперь массив выглядит так:

Мы видим, что цифра 7 заняла первую позицию в массиве, так как она не иметь любую цифру десятков. Мы могли бы также думать об этом как о 0 в разряде десятков.

Итерация 3:

Перейдем к разряду сотен:

После этой итерации массив выглядит так:

И здесь алгоритм останавливается, все элементы отсортированы.

4. Реализация

Давайте теперь посмотрим на реализацию. 

void sort(int[] numbers) {
    int maximumNumber = findMaximumNumberIn(numbers);
    int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber);
    int placeValue = 1;
    while (numberOfDigits-- > 0) {
        applyCountingSortOn(numbers, placeValue);
        placeValue *= 10;
    }
}

Алгоритм работает, находя максимальное число в массиве и затем вычисляя его длину. Этот шаг помогает нам убедиться, что мы выполняем подпрограмму для каждого разряда.

Например, в массиве [7, 37, 68, 123, 134, 221, 387, 468, 769] максимальное число равно 769, а его длина равна 3.

Итак, итерируем и применяем подпрограмма трижды по цифрам в каждой позиции: 

void applyCountingSortOn(int[] numbers, int placeValue) {

    int range = 10 // decimal system, numbers from 0-9

    // ...

    // calculate the frequency of digits
    for (int i = 0; i < length; i++) {
        int digit = (numbers[i] / placeValue) % range;
        frequency[digit]++;
    }

    for (int i = 1; i < range; i++) {
        frequency[i] += frequency[i - 1];
    }

    for (int i = length - 1; i >= 0; i--) {
        int digit = (numbers[i] / placeValue) % range;
        sortedValues[frequency[digit] - 1] = numbers[i];
        frequency[digit]--;
    }

    System.arraycopy(result, 0, numbers, 0, length); 

}

В подпрограмме мы использовали систему счисления (диапазон) для подсчета появления каждой цифры и увеличения ее частоты. Таким образом, каждый бин в диапазоне от 0 до 9 будет иметь некоторое значение, основанное на частоте цифр. Затем мы используем частоту для позиционирования каждого элемента в массиве. Это также помогает нам минимизировать пространство, необходимое для сортировки массива.

Теперь давайте проверим наш метод: 

@Test
public void givenUnsortedArray_whenRadixSort_thenArraySorted() {
    int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7};
    RadixSort.sort(numbers);
    int[] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769};
    assertArrayEquals(numbersSorted, numbers); 
}

5. Сортировка по основанию и сортировка подсчетом

В подпрограмме длина массива частот равна 10 (0-9). В случае сортировки подсчетом мы не используем диапазон. Длина массива частот будет равна максимальному числу в массиве + 1. Поэтому мы не делим их на ячейки, тогда как Radix Sort использует ячейки для сортировки.

Сортировка подсчетом весьма эффективна, когда длина массива ненамного меньше максимального значения в массиве, тогда как сортировка по основанию допускает большие значения в массиве.

6. Сложность

Производительность сортировки по основанию зависит от стабильного алгоритма сортировки, выбранного для сортировки цифр.

Здесь мы использовали сортировку по основанию для сортировки массива из n чисел по основанию b. В нашем случае основание равно 10. Мы применили сортировку подсчетом d раз, где d обозначает количество цифр. Таким образом, временная сложность Radix Sort становится O (d * (n + b)).

Объемная сложность равна O(n + b), так как здесь мы использовали вариант сортировки подсчетом в качестве подпрограммы.

7. Заключение

В этой статье мы описали алгоритм сортировки по основанию и проиллюстрировали, как его реализовать.

«Как обычно, реализации кода доступны на Github.