«Сортировка подсчетом в Java»

«1. Обзор

Алгоритмы сортировки общего назначения, такие как сортировка слиянием, не делают предположений о входных данных, поэтому они не могут превзойти O(n log n) в худшем случае. Сортировка подсчетом, напротив, имеет предположение о входных данных, что делает его алгоритмом линейной сортировки по времени.

В этом уроке мы познакомимся с механикой сортировки подсчетом, а затем реализуем ее на Java.

2. Сортировка подсчетом

Сортировка подсчетом, в отличие от большинства классических алгоритмов сортировки, не сортирует входные данные путем сравнения элементов. Вместо этого предполагается, что входными элементами являются n целых чисел в диапазоне [0, k]. Когда k = O(n), сортировка подсчетом будет выполняться за время O(n).

Обратите внимание, что мы не можем использовать сортировку подсчетом в качестве алгоритма сортировки общего назначения. Однако, когда ввод соответствует этому предположению, это происходит довольно быстро!

2.1. Частотный массив

Предположим, мы собираемся отсортировать входной массив со значениями в диапазоне [0, 5]:

Сначала мы должны подсчитать появление каждого числа во входном массиве. Если мы представим отсчеты массивом C, то C[i] представляет частоту числа i во входном массиве:

Например, поскольку 5 встречается во входном массиве 3 раза, значение для индекса 5 равно 3.

Теперь, имея массив C, мы должны определить, сколько элементов меньше или равно каждому входному элементу. Например:

Один элемент меньше или равен нулю, или другими словами, существует только одно нулевое значение, равное C[0] Два элемента меньше или равны единице, что равно C[0] + C[1] Четыре значения меньше или равны двум, что равно C[0] + C[1] + C[2]

Итак, если мы продолжим вычислять сумму n последовательных элементов в C, мы можем знать, сколько элементов меньше или равно числу n-1 во входном массиве. В любом случае, применяя эту простую формулу, мы можем обновить C следующим образом:

2.2. Алгоритм

Теперь мы можем использовать вспомогательный массив C для сортировки входного массива. Вот как работает сортировка подсчетом:

Она перебирает входной массив в обратном порядке. Для каждого элемента i C[i] — 1 представляет положение числа i в отсортированном массиве. Это связано с тем, что есть элементы C[i] меньше или равные i Затем он уменьшает C[i] в ​​конце каждого раунда

Чтобы отсортировать выборочный входной массив, мы должны сначала начните с числа 5, так как это последний элемент. Согласно C[5], есть 11 элементов, меньших или равных числу 5.

Итак, 5 должен быть 11-м элементом в отсортированном массиве, следовательно, индекс 10:

Поскольку мы переместили 5 в отсортированный массив, мы должны уменьшить C[5]. Следующий элемент в обратном порядке равен 2. Поскольку есть 4 элемента, меньших или равных 2, это число должно быть 4-м элементом в отсортированном массиве:

Аналогично, мы можем найти правильное место для следующего элемента, который 0:

Если мы продолжим итерацию в обратном порядке и переместим каждый элемент соответствующим образом, мы получим что-то вроде:

3. Сортировка подсчетом — реализация Java

3.1. Вычисление массива частот

Во-первых, учитывая входной массив элементов и k, мы должны вычислить массив C:

int[] countElements(int[] input, int k) {
    int[] c = new int[k + 1];
    Arrays.fill(c, 0);

    for (int i : input) {
        c[i] += 1;
    }

    for (int i = 1; i < c.length; i++) {
	c[i] += c[i - 1];
    }

    return c;
}

Давайте разберем сигнатуру метода:

input представляет собой массив чисел, который мы re собирается отсортировать Входной массив — это массив целых чисел в диапазоне [0, k] — таким образом, k представляет собой максимальное число на входе Тип возвращаемого значения — это массив целых чисел, представляющий массив C

А вот как работает метод countElements:

Сначала мы инициализировали массив C. Поскольку диапазон [0, k] содержит k+1 чисел, мы создаем массив, способный содержать k+1 чисел Затем для каждого числа во входных данных мы вычисляем частоту этого числа И, наконец, мы сложение последовательных элементов вместе, чтобы узнать, сколько элементов меньше или равно определенному числу

Кроме того, мы можем проверить, что метод countElements работает должным образом:

@Test
void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected() {
    int k = 5;
    int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 };
    
    int[] c = CountingSort.countElements(input, k);
    int[] expected = { 1, 2, 4, 6, 8, 11 };
    assertArrayEquals(expected, c);
}

3.2. Сортировка входного массива

«Теперь, когда мы можем вычислить массив частот, мы должны иметь возможность сортировать любой заданный набор чисел:

int[] sort(int[] input, int k) {
    int[] c = countElements(input, k);

    int[] sorted = new int[input.length];
    for (int i = input.length - 1; i >= 0; i--) {
        int current = input[i];
	sorted[c[current] - 1] = current;
	c[current] -= 1;
    }

    return sorted;
}

Вот как работает метод сортировки:

Сначала он вычисляет массив C. Затем он перебирает входные данные. array в обратном порядке и для каждого элемента на входе находит правильное место в отсортированном массиве. i-й элемент во входных данных должен быть C[i]-м элементом в отсортированном массиве. Поскольку массивы Java имеют нулевой индекс, запись C[i]-1 является элементом C[i]-го — например, sorted[5] — это шестой элемент в отсортированном массиве. Каждый раз, когда мы находим совпадение, он уменьшает соответствующее значение C[i]

Точно так же мы можем проверить, что метод сортировки работает должным образом:

@Test
void sort_GivenAnArray_ShouldSortTheInputAsExpected() {
    int k = 5;
    int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 };

    int[] sorted = CountingSort.sort(input, k);

    // Our sorting algorithm and Java's should return the same result
    Arrays.sort(input);
    assertArrayEquals(input, sorted);
}

4. Пересмотр алгоритма сортировки подсчетом

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

Большинство классических алгоритмов сортировки, таких как сортировка слиянием, сортируют любой заданный ввод, просто сравнивая входные элементы друг с другом. Этот тип алгоритмов сортировки известен как сортировка сравнением. В худшем случае сортировка сравнением должна занимать не менее O(n log n) для сортировки n элементов.

Сортировка подсчетом, с другой стороны, не сортирует входные данные путем сравнения входных элементов, так что это явно не алгоритм сортировки сравнением.

Давайте посмотрим, сколько времени он тратит на сортировку входных данных:

Он вычисляет массив C за время O(n+k): Он один раз перебирает входной массив размера n за O(n), а затем итерирует C в O(k) — так что всего будет O(n+k) После вычисления C он сортирует входные данные, перебирая входной массив и выполняя несколько примитивных операций на каждой итерации. Таким образом, фактическая операция сортировки занимает O(n)

В целом, сортировка с подсчетом занимает O(n+k) времени для выполнения:

O(n + k) + O(n) = O(2n + k) = O(n + k)

Если предположить, что k=O(n), то алгоритм сортировки с подсчетом сортирует ввод за линейное время. В отличие от алгоритмов сортировки общего назначения, сортировка с подсчетом делает предположение о входных данных и требует меньше, чем нижняя граница O (n log n) для выполнения.

4.2. Стабильность

Несколько минут назад мы установили несколько своеобразных правил, касающихся механики сортировки подсчетом, но так и не прояснили их причину. Чтобы быть более конкретным:

Почему мы должны перебирать входной массив в обратном порядке? Почему мы уменьшаем значение C[i] каждый раз, когда используем его?

Давайте повторим сначала, чтобы лучше понять первое правило. Предположим, мы собираемся отсортировать простой массив целых чисел, например следующий:

В первой итерации мы должны найти отсортированное местоположение для первой 1:

Таким образом, первое вхождение числа 1 получает последний индекс в отсортированный массив. Пропустив число 0, давайте посмотрим, что произойдет со вторым вхождением числа 1:

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

Что произойдет, если мы не будем уменьшать значение C[i] после каждого использования? Посмотрим:

Оба вхождения числа 1 занимают последнее место в отсортированном массиве. Поэтому, если мы не будем уменьшать значение C[i] после каждого использования, мы потенциально можем потерять несколько чисел при их сортировке!

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

В этом уроке мы сначала узнали, как работает сортировка подсчетом внутри. Затем мы реализовали этот алгоритм сортировки на Java и написали несколько тестов для проверки его поведения. И, наконец, мы доказали, что алгоритм является устойчивым алгоритмом сортировки с линейной временной сложностью.

Как обычно, примеры кода доступны в нашем проекте на GitHub, так что обязательно ознакомьтесь с ним!