Учитывая коллекцию n элементов, каждый из которых имеет неотрицательный целочисленный ключ, максимальное значение которого не превышает k, эффективно отсортируйте его, используя алгоритм сортировки подсчетом.
Обзор
Сортировка подсчетом — это алгоритм сортировки на основе целых чисел для сортировки массива, ключи которого лежат в определенном диапазоне. Он подсчитывает общее количество элементов с каждым уникальным значением ключа, а затем использует эти подсчеты для определения позиций каждого значения ключа в выходных данных.
Мы можем использовать сортировку подсчетом, чтобы найти наиболее часто встречающуюся букву в файле или эффективно отсортировать массив с ограниченным диапазоном. Он часто используется в качестве подпрограммы в алгоритме сортировки по основанию, поэтому сортировка подсчетом должна быть стабильной.
Алгоритм
Алгоритм циклически перебирает элементы, вычисляя гистограмму количества раз, когда каждый ключ входил во входную коллекцию. Затем он выполняет вычисление суммы префиксов, чтобы определить для каждого ключа начальную позицию в выходном массиве элементов, имеющих этот ключ. Наконец, он снова перебирает элементы, перемещая каждый элемент в его отсортированную позицию в выходном массиве.
Алгоритм может быть реализован, как показано ниже, на C, Java и Python. В приведенном ниже коде:
- После первого цикла for
freq[i]хранит общее количество элементов с ключом, равнымi. - После второго цикла for он вместо этого сохраняет общее количество элементов с ключом меньше
i, который совпадает с первым индексом, по которому элемент с ключомiдолжны храниться в выходном массиве. - На протяжении третьего цикла,
freq[i]всегда сохраняет следующую позицию в выходном массиве, в которой элемент с ключомiдолжны быть сохранены, поэтому каждый элемент перемещается в правильное положение в выходном массиве.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <stdio.h> #include <string.h> /* `arr` ——> входной целочисленный массив для сортировки `n` ——> длина входного массива `k` ——> такое число, что все целые числа находятся в диапазоне `0…k-1` */ void countsort(int arr[], int n, int k) { // создаем целочисленный массив размера `n` для хранения отсортированного массива int output[n]; // создать целочисленный массив размером `k + 1`, инициализированный всеми нулями int freq[k + 1]; memset(freq, 0, sizeof(freq)); // 1. Используя значение каждого элемента входного массива в качестве индекса, // сохраняем счетчик каждого целого числа в `freq[]` for (int i = 0; i < n; i++) { freq[arr[i]]++; } // 2. Вычислить начальный индекс для каждого целого числа int total = 0; for (int i = 0; i < k + 1; i++) { int oldCount = freq[i]; freq[i] = total; total += oldCount; } // 3. Копируем в выходной массив, сохраняя порядок входов с одинаковыми ключами for (int i = 0; i < n; i++) { output[freq[arr[i]]] = arr[i]; freq[arr[i]]++; } // копируем выходной массив обратно во входной массив for (int i = 0; i < n; i++) { arr[i] = output[i]; } } int main() { int arr[] = { 4, 2, 10, 10, 1, 4, 2, 1, 10 }; int n = sizeof(arr) / sizeof(arr[0]); // диапазон элементов массива int k = 10; countsort(arr, n, k); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; } |
результат:
1 1 2 2 4 4 10 10 10
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import java.util.Arrays; class Main { /* `arr` ——> входной целочисленный массив для сортировки `k` ——> такое число, что все целые числа находятся в диапазоне `0…k-1` */ public static void countsort(int[] arr, int k) { // создаем целочисленный массив размера `n` для хранения отсортированного массива int[] output = new int[arr.length]; // создать целочисленный массив размером `k + 1`, инициализированный всеми нулями int[] freq = new int[k + 1]; // используя значение каждого элемента входного массива в качестве индекса, // сохраняем счетчик каждого целого числа в `freq[]` for (int i: arr) { freq[i]++; } // вычисляем начальный индекс для каждого целого числа int total = 0; for (int i = 0; i < k + 1; i++) { int oldCount = freq[i]; freq[i] = total; total += oldCount; } // копируем в выходной массив, сохраняя порядок входов с одинаковыми ключами for (int i: arr) { output[freq[i]] = i; freq[i]++; } // копируем выходной массив обратно во входной массив Arrays.setAll(arr, i -> output[i]); } public static void main(String[] args) { int[] arr = { 4, 2, 10, 10, 1, 4, 2, 1, 10 }; // диапазон элементов массива int k = 10; countsort(arr, k); System.out.println(Arrays.toString(arr)); } } |
результат:
[1, 1, 2, 2, 4, 4, 10, 10, 10]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
''' `A` ——> the input list of integers to be sorted `k` ——> a number such that all integers are in range `0…k-1` ''' def countsort(A, k): # создает целочисленный список размера `n` для хранения отсортированного списка output = [0] * len(A) # создает целочисленный список размером `k + 1`, инициализированный всеми нулями freq = [0] * (k + 1) #, используя значение каждого элемента в списке ввода в качестве индекса, # сохраняет счетчик каждого целого числа в `freq[]` for i in A: freq[i] = freq[i] + 1 # вычисляет начальный индекс для каждого целого числа total = 0 for i in range(k + 1): oldCount = freq[i] freq[i] = total total += oldCount # копирует в список выходов, сохраняя порядок входов с одинаковыми ключами for i in A: output[freq[i]] = i freq[i] = freq[i] + 1 # скопировать список вывода обратно в список ввода for i in range(len(A)): A[i] = output[i] if __name__ == '__main__': A = [4, 2, 10, 10, 1, 4, 2, 1, 10] # диапазон элементов списка k = 10 countsort(A, k) print(A) |
результат:
[1, 1, 2, 2, 4, 4, 10, 10, 10]
В отличие от других алгоритмов сортировки, таких как Сортировка вставками, Сортировка выбором, Сортировка слиянием, Быстрая сортировкаи т. д., сортировка подсчетом не является сортировкой сравнением. Он использует ключевые значения в качестве индексов в массиве, как видно из приведенного выше кода.
Ниже приведена более простая версия сортировки подсчетом, которая не дает стабильной сортировки, т. е. относительный порядок элементов с одинаковыми ключами больше не сохраняется.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <stdio.h> #include <string.h> /* `arr` ——> входной целочисленный массив для сортировки `n` ——> длина входного массива `k` ——> такое число, что все целые числа находятся в диапазоне `0…k-1` */ void countsort(int arr[], int n, int k) { // создаем целочисленный массив размером `k + 1` для хранения счетчика каждого целого числа // во входном массиве int freq[k + 1]; // инициализируем целочисленный массив 0 memset(freq, 0, sizeof(freq)); // используя значение каждого элемента входного массива в качестве индекса, // сохраняем счетчик каждого целого числа в `freq[]` for (int i = 0; i < n; i++) { freq[arr[i]]++; } // перезаписываем входной массив в порядке сортировки int index = 0; for (int i = 0; i < k + 1; i++) { while (freq[i]--) { arr[index++] = i; } } } int main() { int arr[] = { 4, 2, 10, 10, 1, 4, 2, 1, 10 }; int n = sizeof(arr) / sizeof(arr[0]); // указываем диапазон элементов массива int k = 10; countsort(arr, n, k); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; } |
результат:
1 1 2 2 4 4 10 10 10
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
import java.util.Arrays; class Main { /* `arr` ——> входной целочисленный массив для сортировки `k` ——> такое число, что все целые числа находятся в диапазоне `0…k-1` */ public static void countsort(int[] arr, int k) { // создаем целочисленный массив размером `k + 1` для хранения счетчика каждого целого числа // во входном массиве int[] freq = new int[k + 1]; // используя значение каждого элемента входного массива в качестве индекса, // сохраняем счетчик каждого целого числа в `freq[]` for (int i: arr) { freq[i]++; } // перезаписываем входной массив в порядке сортировки int index = 0; for (int i = 0; i < k + 1; i++) { while (freq[i]-- > 0) { arr[index++] = i; } } } public static void main(String[] args) { int[] arr = { 4, 2, 10, 10, 1, 4, 2, 1, 10 }; // диапазон элементов массива int k = 10; countsort(arr, k); System.out.println(Arrays.toString(arr)); } } |
результат:
[1, 1, 2, 2, 4, 4, 10, 10, 10]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
''' `A` ——> the input list of integers to be sorted `k` ——> a number such that all integers are in range `0…k-1` ''' def countsort(A, k): # создает список целых чисел размером `k + 1` для хранения количества каждого целого числа. # в списке ввода freq = [0] * (k + 1) #, используя значение каждого элемента в списке ввода в качестве индекса, # сохраняет счетчик каждого целого числа в `freq[]` for i in A: freq[i] += 1 # перезаписывает входной список в отсортированном порядке index = 0 for i in range(k + 1): while freq[i] > 0: A[index] = i index += 1 freq[i] -= 1 if __name__ == '__main__': A = [4, 2, 10, 10, 1, 4, 2, 1, 10] # диапазон элементов списка k = 10 countsort(A, k) print(A) |
результат:
[1, 1, 2, 2, 4, 4, 10, 10, 10]
Производительность
Временная сложность сортировки подсчетом O(n + k), куда n размер ввода и k является входным диапазоном. Поскольку он использует массивы длины k+1 а также n, общее пространство, используемое алгоритмом, также равно O(n + k). Сортировка подсчетом может быть очень эффективной, когда диапазон ключей k значительно меньше, чем общее количество элементов n, но когда вариация ключей значительно превышает общее количество элементов k >> n, сортировка подсчетом занимает много места.
Упражнение:
1. Расширьте решение для обработки отрицательных целых чисел.
2. Укажите точный диапазон ключей, рассчитав максимальную и минимальную разницу значений ключей.
Использованная литература: https://en.wikipedia.org/wiki/Counting_sort