- Сортировка подсчётом
-
Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла[уточнить], так как каждый элемент придётся просматривать более одного раза.
Предположим, что входной массив состоит из целых чисел в диапазоне от до , где . Далее алгоритм будет обобщён для произвольного целочисленного диапазона. Существует несколько модификаций сортировки подсчётом, ниже рассмотрены три линейных и одна квадратичная, которая использует другой подход, но имеет то же название.
Содержание
Простой алгоритм
Это простейший вариант алгоритма. Создать вспомогательный массив
C[0..k - 1]
, состоящий из нулей, затем последовательно прочитать элементы входного массиваA
, для каждогоA[i]
увеличитьC[A[i]]
на единицу. Теперь достаточно пройти по массивуC
, для каждого в массивA
последовательно записать числоj C[j]
раз.SimpleCountingSort for i = 0 to k - 1 C[i] = 0; for i = 0 to n - 1 C[A[i]] = C[A[i]] + 1; b = 0; for j = 0 to k - 1 for i = 0 to C[j] - 1 A[b] = j; b = b + 1;
Алгоритм со списком
Этот вариант (англ. pigeonhole sorting, count sort) используется, когда на вход подается массив структур данных, который следует отсортировать по ключам (
key
). Нужно создать вспомогательный массивC[0..k - 1]
, каждыйC[i]
в дальнейшем будет содержать список элементов из входного массива. Затем последовательно прочитать элементы входного массиваA
, каждыйA[i]
добавить в списокC[A[i].key]
. В заключении пройти по массивуC
, для каждого в массивA
последовательно записывать элементы спискаC[j]
. Алгоритм устойчив.ListCountingSort for i = 0 to k - 1 C[i] = NULL; for i = 0 to n - 1 C[A[i].key].add(A[i]); b = 0; for j = 0 to k - 1 p = C[j]; while p != NULL A[b] = p.data; p = p.next(); b = b + 1;
Устойчивый алгоритм
В этом варианте помимо входного массива
A
потребуется два вспомогательных массива —C[0..k - 1]
для счётчика иB[0..n - 1]
для отсортированного массива. Сначала следует заполнить массивC
нулями, и для каждогоA[i]
увеличитьC[A[i]]
на 1. Далее подсчитывается количество элементов меньших или равных . Для этого каждыйC[j]
, начиная сC[1]
, увеличивают наC[j - 1]
. Таким образом в последней ячейке будет находиться количество элементов от до существующих во входном массиве. На последнем шаге алгоритма читается входной массив с конца, значениеC[A[i]]
уменьшается на 1 и в каждыйB[C[A[i]]]
записываетсяA[i]
. Алгоритм устойчив.StableCountingSort for i = 0 to k - 1 C[i] = 0; for i = 0 to n - 1 C[A[i]] = C[A[i]] + 1; for j = 1 to k - 1 C[j] = C[j] + C[j - 1]; for i = n - 1 to 0 C[A[i]] = C[A[i]] - 1; B[C[A[i]]] = A[i];
Обобщение на произвольный целочисленный диапазон
Возникает несколько вопросов. Что делать, если диапазон значений (min и max) заранее не известен? Что делать, если минимальное значение больше нуля или в сортируемых данных присутствуют отрицательные числа? Первый вопрос можно решить линейным поиском min и max, что не повлияет на асимптотику алгоритма. Второй вопрос несколько сложнее. Если min больше нуля, то следует при работе с массивом
C
изA[i]
вычитать min, а при обратной записи прибавлять. При наличии отрицательных чисел нужно при работе с массивомC
кA[i]
прибавлять |min|, а при обратной записи вычитать.Анализ
В первых двух алгоритмах первые два цикла работают за и , соответственно; двойной цикл за . В третьем алгоритме циклы занимают , , и , соответственно. Итого все три алгоритма имеют линейную временную трудоёмкость . Используемая память в первых двух алгоритмах равна , а в третьем .
Квадратичный алгоритм сортировки подсчётом
Также сортировкой подсчётом называют немного другой алгоритм. В нём используются входной массив
A
и вспомогательный массивB
для отсортированного множества. В алгоритме следует для каждого элемента входного массиваA[i]
подсчитать количество элементов меньших него и количество элементов, равных ему, но стоящих ранее ().B[c]
присвоитьA[i]
. Алгоритм устойчив.SquareCountingSort for i = 0 to n - 1 c = 0; for j = 0 to i - 1 if A[j] <= A[i] c = c + 1; for j = i + 1 to n - 1 if A[j] < A[i] c = c + 1; B[c] = A[i];
Анализ
Очевидно, временная оценка алгоритма равна , память .
Примеры реализации
C
Простой алгоритм.
void CountingSort (int *a, int n, int min, int max) { int i, j, c; int *b; assert(n > 0); assert(min <= max); b = (int *)calloc(max - min + 1, sizeof(int)); assert(b != NULL); for (i = 0; i <= n - 1; ++i) ++b[a[i] - min]; for (j = min; j <= max; ++j) { c = b[j - min]; while (c > 0) { *a = j; ++a; --c; } } free(b); }
С++
int a[q],b[q],i,j; for (i = 0; i < q; i++) { j = i; while (j > 0 && b[j-1] > a[i]) { b[j] = b[j-1]; j = j - 1; } b[j] = a[i]; }
Компонентный Паскаль
Простой алгоритм.
PROCEDURE CountingSort (VAR a: ARRAY OF INTEGER; min, max: INTEGER); VAR i, j, c: INTEGER; b: POINTER TO ARRAY OF INTEGER; BEGIN ASSERT(min <= max); NEW(b, max - min + 1); FOR i := 0 TO LEN(a) - 1 DO INC(b[a[i] - min]) END; i := 0; FOR j := min TO max DO c := b[j - min]; WHILE c > 0 DO a[i] := j; INC(i); DEC(c) END END END CountingSort;
См. также
Литература
- Ананий В. Левитин Глава 7. Пространственно-временной компромисс: Сортировка подсчетом // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 307 - 310. — ISBN 5-8459-0987-2
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — С. 224 - 226. — ISBN 5-8459-0857-4
Ссылки
- Визуализатор1 — Java-аплет.
- Визуализатор2 — Java-аплет.
У этой статьи нет иллюстраций. Вы можете помочь проекту, добавив их (с соблюдением правил использования изображений).
Для поиска иллюстраций можно:- попробовать воспользоваться инструментом FIST: нажмите эту ссылку, чтобы начать поиск;
- попытаться найти изображение на Викискладе;
- просмотреть иноязычные варианты статьи (если они есть);
- см. также Википедия:Источники изображений.
Алгоритмы сортировки Теория Сложность • О-нотация • Отношение порядка • Типы сортировки: Устойчивая • Внутренняя • Внешняя
Алгоритмы Обменные: Пузырьком • Перемешиванием • Гномья • Быстрая • Расчёской • Выбором: Выбором • Пирамидальная • Вставками: Вставками • Шелла • Деревом • Слиянием: Слиянием • Без дополнительной памяти • Без сравнений: Подсчётом • Поразрядная • Блочная • Гибридные: Introsort • Timsort • Прочее: Топологическая • Сети • Непрактичные: Bogosort • Stooge sort • Глупая • Блинная
Категория:- Алгоритмы сортировки
Wikimedia Foundation. 2010.