Журнал фильтра правок

''''Сортировка подсчётом''' — [[алгоритм сортировки]], в котором используется диапазон чисел сортируемого [[массив]]а ([[Список (информатика)|списка]]) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла{{уточнить}}, так как каждый элемент придётся просматривать более одного раза. Предположим, что входной массив состоит из <math>n</math> целых чисел в диапазоне от <math>0</math> до <math>k - 1</math>, где <math>k \in \mathbb N</math>. Далее алгоритм будет обобщён для произвольного целочисленного диапазона. Существует несколько модификаций сортировки подсчётом, ниже рассмотрены три линейных и одна квадратичная, которая использует другой подход, но имеет то же название. == Простой алгоритм == Это простейший вариант алгоритма. Создать вспомогательный массив <code>C[0..k - 1]</code>, состоящий из нулей, затем последовательно прочитать элементы входного массива <code>A</code>, для каждого <code>A[i]</code> увеличить <code>C[A[i]]</code> на единицу. Теперь достаточно пройти по массиву <code>C</code>, для каждого <math>j \in \{0, ..., k - 1\}</math> в массив <code>A</code> последовательно записать число <code>j C[j]</code> раз. <code> 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;</code> == Алгоритм со списком == Этот вариант ({{lang-en|pigeonhole sorting, count sort}}) используется, когда на вход подается массив структур данных, который следует отсортировать по ключам (<code>key</code>). Нужно создать вспомогательный массив <code>C[0..k - 1]</code>, каждый <code>C[i]</code> в дальнейшем будет содержать список элементов из входного массива. Затем последовательно прочитать элементы входного массива <code>A</code>, каждый <code>A[i]</code> добавить в список <code>C[A[i].key]</code>. В заключении пройти по массиву <code>C</code>, для каждого <math>j \in \{0, ..., k - 1\}</math> в массив <code>A</code> последовательно записывать элементы списка <code>C[j]</code>. [[устойчивая сортировка|Алгоритм устойчив]]. <code> 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;</code> == Устойчивый алгоритм == В этом варианте помимо входного массива <code>A</code> потребуется два вспомогательных массива — <code>C[0..k - 1]</code> для счётчика и <code>B[0..n - 1]</code> для отсортированного массива. Сначала следует заполнить массив <code>C</code> нулями, и для каждого <code>A[i]</code> увеличить <code>C[A[i]]</code> на 1. Далее подсчитывается количество элементов меньших или равных <math>k - 1</math>. Для этого каждый <code>C[j]</code>, начиная с <code>C[1]</code>, увеличивают на <code>C[j - 1]</code>. Таким образом в последней ячейке будет находиться количество элементов от <math>0</math> до <math>k - 1</math> существующих во входном массиве. На последнем шаге алгоритма читается входной массив с конца, значение <code>C[A[i]]</code> уменьшается на 1 и в каждый <code>B[C[A[i]]]</code> записывается <code>A[i]</code>. Алгоритм устойчив. <code> 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];</code> == Обобщение на произвольный целочисленный диапазон == Возникает несколько вопросов. Что делать, если диапазон значений (min и max) заранее не известен? Что делать, если минимальное значение больше нуля или в сортируемых данных присутствуют отрицательные числа? Первый вопрос можно решить линейным поиском min и max, что не повлияет на асимптотику алгоритма. Второй вопрос несколько сложнее. Если min больше нуля, то следует при работе с массивом <code>C</code> из <code>A[i]</code> вычитать min, а при обратной записи прибавлять. При наличии отрицательных чисел нужно при работе с массивом <code>C</code> к <code>A[i]</code> прибавлять |min|, а при обратной записи вычитать. == Анализ == В первых двух алгоритмах первые два цикла работают за [[Теория сложности вычислений|<math>\Theta(k)</math>]] и <math>\Theta(n)</math>, соответственно; двойной цикл за <math>\Theta(n + k)</math>. В третьем алгоритме циклы занимают <math>\Theta(k)</math>, <math>\Theta(n)</math>, <math>\Theta(k)</math> и <math>\Theta(n)</math>, соответственно. Итого все три алгоритма имеют линейную временную трудоёмкость <math>\Theta(n + k)</math>. Используемая память в первых двух алгоритмах равна <math>\Theta(k)</math>, а в третьем <math>\Theta(n + k)</math>. == Квадратичный алгоритм сортировки подсчётом == Также сортировкой подсчётом называют немного другой алгоритм. В нём используются входной массив <code>A</code> и вспомогательный массив <code>B</code> для отсортированного множества. В алгоритме следует для каждого элемента входного массива <code>A[i]</code> подсчитать количество элементов меньших него <math>c_1</math> и количество элементов, равных ему, но стоящих ранее <math>c_2</math> (<math>c = c_1 + c_2</math>). <code>B[c]</code> присвоить <code>A[i]</code>. Алгоритм устойчив. <code> 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];</code> === Анализ === Очевидно, временная оценка алгоритма равна <math>\Theta(n^2)</math>, память <math>\Theta(n)</math>. == Примеры реализации == === C === Простой алгоритм. <source lang="c"> void counting_sort (int *vec, int len, int min, int max) { assert(len > 0); assert(min <= max); assert(vec != NULL); int cnt[max-min+1]; for(int i = min; i <= max; ++i) cnt[i - min] = 0; for(int i = 0; i < len; ++i) ++cnt[vec[i] - min]; for(int i = min; i <= max; ++i) for(int j = cnt[i - min]; j--;) *vec++ = i; }</source> === С++ === <source lang="cpp"> 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; } b[j] = a[i]; } </source> === [[Компонентный Паскаль]] === Простой алгоритм. <source lang="pascal"> 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; </source> == См. также == * [[Алгоритм сортировки]] * [[O-большое]] * [[Временная сложность алгоритма]] == Литература == * {{книга |часть = '''Глава 7. Пространственно-временной компромисс: Сортировка подсчетом''' |заглавие = Алгоритмы: введение в разработку и анализ |оригинал = Introduction to The Design and Analysis of Aigorithms |автор = Ананий В. Левитин |ссылка = |isbn = 5-8459-0987-2 |страницы = 307 - 310 |год = 2006 |место = М. |издательство = [[Вильямс (издательство)|«Вильямс»]] }} * {{книга |часть = '''Глава 8. Сортировка за линейное время''' |заглавие = Алгоритмы: построение и анализ |оригинал = Introduction to Algorithms |автор = Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд |ссылка = |издание = 2-e издание |isbn = 5-8459-0857-4 |страницы = 224 - 226 |год = 2005 |место = М. |издательство = [[Вильямс (издательство)|«Вильямс»]] }} == Ссылки == * [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2005 Визуализатор1] — Java-аплет. * [http://rain.ifmo.ru/cat/view.php/vis/sorts/linear-2001 Визуализатор2] — Java-аплет. {{нет иллюстраций}} {{Алгоритмы сортировки}} [[Категория:Алгоритмы сортировки]] [[cs:Counting sort]] [[de:Countingsort]] [[en:Counting sort]] [[es:Ordenamiento por cuentas]] [[fa:مرتب‌سازی شمارشی]] [[fi:Laskentalajittelu]] [[fr:Tri comptage]] [[he:מיון מנייה]] [[hy:Հաշվողական տեսակավորում]] [[it:Counting sort]] [[ml:കൗണ്ടിങ്ങ് സോർട്ട്]] [[nl:Counting sort]] [[pl:Sortowanie przez zliczanie]] [[pt:Counting sort]] [[sk:Counting sort]] [[tr:Sayarak sıralama]] [[uk:Сортування підрахунком]] [[zh:计数排序]]'