Сортировка подсчётом

Введение

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

Сортировка целых чисел

Это наиболее простая версия алгоритма. Имеется начальный числовой набор, длиной nn, а итоги сортировки буду сохранены в массиве АА. Создадим для удобства работы некий служебный массив СС, который обладает индексацией от нуля до k−1k−1 и в исходном состоянии заполнен нулевыми значениями. Очерёдность действий в алгоритме, следующая:

1. Выполняется проход по массиву АА и запись в C[i]C[i] количества чисел, которые равны ii.
2. Выполняется проход по массиву СС, где для всех number∈{0,...,k−1}number∈{0,...,k−1} в массив АА поочерёдно пишется число C[number]C[number] раз.

Ниже приведена программная реализация алгоритма на уровне псевдокодов:

Рисунок 1. Псевдокод. Автор24 — интернет-биржа студенческих работ

Выполнение сортировки сложных объектов

Часто возникает проблема сортировки сложных информационных объектов, под которыми понимается структурное построение, которое содержит несколько полей. Одно из этих полей необходимо выделить и обозначить как ключ. Сортировка производится по этому ключу, диапазон целочисленных значений ключа простирается от нуля до k−1k−1. Но в данном случае, нельзя применять алгоритм сортировки подсчётом целых чисел, так как в общем списке возможно наличие разных структур, но с одинаковыми ключами. Есть два метода обойти эту проблему, а именно, применять списки, хранящие структуры в прошедшем сортировку массиве, или определить заранее число структур, которые имеют одинаковые ключи. Причём сделать это надо для каждого значения ключа. Итак, начальный набор из nn структур сохраняется в массиве АА, а прошедшие сортировку структуры записываются в массив ВВ, который имеет такой же объём. И в добавок, применяется служебный массив РР, имеющий индексацию от нуля до k−1k−1.

Основная концепция алгоритма заключается в предварительном определении числа элементов с разными ключами в начальном массиве и подразделении итогового массива на участки необходимого размера (блоки). Далее при следующем обходе начального массива копия каждого его компонента записывается в специальный блок с ключами этого размера, в первую не занятую ячейку. Делать эту процедуру помогает массив индексов РР, хранящий индексы начала блоков для всех размеров ключей. P[key]P[key] обозначает индексацию итогового массива, которая соответствует начальному компоненту блока для ключа keykey. Очерёдность операций в алгоритме, следующая:

1. Выполняется проход по начальному массиву АА и запись в P[i]P[i] числа структур с ключом, равным ii.
2. Массив ВВ условно подразделяется на kk блоков, с длиной каждого из них, равной P[0]P[0], P[1]P[1], ..., P[k]P[k].
3. Поскольку массив РР больше не потребуется, он преобразуется в массив P[i]P[i], который будет сохранять сумму компонентов от нуля до i−1i−1 бывшего массива PP.
4. Выполняется сдвиг массива РР на один компонент вперёд. В новом массиве P[0]=0P[0]=0, а для i>0i>0 P[i]=Pold[i−1]P[i]=Pold[i−1]. Здесь PoldPold является прежним массивом PP. Такое действие возможно выполнить в течение одного прохода по массиву РР, и даже единовременно с выполнением предыдущего шага. По завершению этой операции, в массиве РР окажутся сохранёнными индексы массива ВВ. P[key]P[key] будет указывать на начальный элемент блока ВВ, который соответствует ключу keykey.
5. Выполняется собственно сортировка. Осуществляется ещё один проход по начальному массиву АА и для всех i∈[0,n−1]i∈[0,n−1] и пересылается структура A[i]A[i] в массив BB на место P[A[i].key]P[A[i].key]. Далее выполняется увеличение P[A[i].key]P[A[i].key] на одиннадцать. Здесь A[i].keyA[i].key является ключом структуры, которая расположена в массиве АА на ii-том месте.

После окончания действия алгоритма в массиве ВВ окажется записанным начальный набор структур, но прошедший сортировку. Блоки располагаются в порядке увеличения значений ключей. Необходимо ещё отметить, что такая сортировка будет устойчивой, поскольку два компонента, имеющие одинаковые ключи, добавляются в такой же очерёдности, в какой выполнялся их просмотр в начальном массиве ВВ. Это свойство определяет существование цифровой сортировки. Ниже приведена программная реализация алгоритма со следующими обозначениями. АА и ВВ являются массивами структур с размером nn и индексацией от нуля до n−1n−1. PP является массивом целых чисел, имеющим размер kk и индексацию от нуля и до k−1k−1, где kk – это число разных ключей.

Рисунок 2. Программа. Автор24 — интернет-биржа студенческих работ

В программе третий и четвёртый пункты алгоритма выполняются в едином цикле и в последнем цикле выполнено копирование всей структуры вместе с ключом.

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

В первом алгоритме (сортировка целых чисел) начальная пара циклов выполняется за Θ(k)Θ(k) и Θ(n)Θ(n). Алгоритм обладает линейной временной трудоёмкостью Θ(n+k)Θ(n+k). Применяемая добавочная память равняется Θ(k)Θ(k). Второй алгоритм имеет в своём составе два обхода массива АА с размером nn и один обход массива РР с размером kk. То есть он обладает трудоёмкостью, равной Θ(n+k)Θ(n+k). При практической реализации, сортировку подсчётом целесообразно использовать, если k=O(n)k=O(n), то есть возможно учитывать время выполнения алгоритма по формуле Θ(n)Θ(n). Аналогично простой сортировке подсчётом, необходимо иметь Θ(n+k)Θ(n+k) добавочной памяти.