Как выполнить сортировку подсчетом на Java?

1. Обзор

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

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

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

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

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

2.1. Массив частот

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

](/lessons/b/-wp-content-uploads-2019-09-counts-png)

Во- первых, мы должны подсчитать появление каждого числа во входном массиве. Если мы представим подсчеты массивом 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 представляет массив чисел, которые мы собираемся сортировать
• Входной массив представляет собой массив целых чисел в диапазоне [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
• Затем он перебирает входной массив в обратном порядке и для каждого элемента на входе находит правильное место в отсортированном массиве. 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 , так что обязательно ознакомьтесь с ним!