Сортировка по основанию в Java

1. Введение

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

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

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

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

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

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

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

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

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

3.1. Итерация 1

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

Итак, давайте начнем с цифр в единицах:

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

Обратите внимание, что числа были отсортированы в соответствии с цифрами в единицах.

3.2. Итерация 2

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

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

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

3.3. Итерация 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. Сложность

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

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

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

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

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

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