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

Пусть исходная последовательность записана в массиве A [1.. n ], C [1.. k ] – вспомогательный массив (k – мощность диапазона чисел, используемых в исходном массиве A [1.. n ]), отсортированная последовательность записывается в массив B [1.. n ].

Counting_Sort (A, B, k)

1. for i:=1 to k

2. do C[i]:=0

3. for j:=1 to length(A)

4. do C[A[j]]:=C[A[j]]+1

5. // C[i] равно количеству элементов, равных i

6. for i:=2 to k

7. do C[i]:=C[i]+C[i-1]

8. // C[i] равно количеству элементов, не превосходящих i

9. for j:= length(A) downto 1

10. do B[C[A[j]]]:=A[j]

11. C[A[j]]:= C[A[j]]-1

 

После инициализации (строки 1 - 2) сначала помещают в С [ i ] количество элементов массива А, равных i (строки 3 - 4), а затем, находя частичные суммы последовательности С [ 1 ], С [2],..., С [ k ] – количество элементов, не превосходящих i (строки 6 - 7). В строках 9-10 каждый из элементов массива А помещается на нужное место в массиве B. В самом деле, если все n элементов различны, то в отсортированном массиве B число A [ j ] должно стоять на месте C [ A [ j ]], ибо именно столько элементов массива A не превосходят числа A [ j ], если в массиве A встречаются повторения, то после каждой записи числа A [ j ] в массив B число C [ A [ j ]] уменьшается на единицу (строка 11), так что при следующей встрече с числом, равным A [ j ], оно будет записано на одну позицию левее.

Пример: исходная последовательность А =,

k =6 – мощность чисел в массиве А, размерность массива А – n=9.

С =, число присваиваний Пр=9, новое значение С [ i ] равно количеству элементов, непревосходящих i (C [ i ]:= C [ i ]+ C [ i -1]),

С =. Пр=Пр+(k -1)=9+(6-1)=14.

 

1. элемент отсортированного массива B [ C [ A [9]]] = A [9], то есть

B [ C [2]] = B [3]= A [9] = 2, значит B [3] = 2 (Пр=Пр+1=15),
далее C [ A [9]]= C [2]= C [2]-1=3-1=2 (Пр=Пр+1=16).

С =.

 

2. B [ C [ A [8]]]= B [ C [1]]= B [2]=1, то есть B [2]=1, C [ A [8]]= C [1]= C [1]-1=2-1=1,

(Пр=Пр+2=18)

 

С =.

 

3. B [ C [ A [7]]]= B [ C [4]]= B [8]= А [7]=4, то есть B [8]=4, C [ A [7]]= C [4]= C [4]-1=7, (Пр=Пр+2=20)

С =.

 

4. B [ C [ A [6]]] = B [ C [4]] = B [7]= А [6]=4, то есть B [7]=4, C [4]= C [4]-1=6, (Пр=Пр+2=22)

С =.

5. B [ C [ A [5]]] = B [ C [1]] = B [1]= А [5]=1, то есть B [1]=1, C [1]= C [1]-1=0, (Пр=Пр+2=24)

С =.

 

6. B [ C [ A [4]]] = B [ C [3]] = B [5]= А [4]=3, то есть B [5]=3, C [3]= C [3]-1=5-1=4, (Пр=Пр+2=26)

С =.

 

И так далее.

Общее количество присваиваний для реализации сортировки подсчетом массива A размерности n =9 и при k =6 – Пр=n+(k-1)+n*2=9+(6-1)+2*9=32.

Таким образом, результирующий массив будет иметь вид

В=

 

 

2. Поразрядная сортировка (LSD)

 

LSD (least significant digit radix sort) - поразрядная сортировка сначала по младшей цифре.

Пусть в общем случае сортируемые числа А =(а ₁, a ₂, …, a _n) являются целыми и состоят из p цифр (более короткие числа дополняются нулями) с основанием системы счисления r. Число а _i имеет следующее представление: a _i=(a _i,p, a _i,p-1, …, a _i,1), где a _i,p – цифра старшего разряда, a _i,1 – цифра младшего разряда числа a _i. Поразрядная сортировка основана на том свойстве, что числа можно полностью отсортировать, выполняя сортировку по отдельным разрядам, начиная с самого младшего.

Алгоритм поразрядной сортировки состоит в следующем:

1) k =1. Выбираем младшую цифру числа.

2) Берем каждое число из массива А и помещаем его в конец одной из r очередей в зависимости от значений цифры в позиции k.

3) Восстанавливаем каждую очередь в массив А, начиная с очереди чисел с цифрой 0 и кончая очередью чисел с (r -1)-й цифрой. (После распределения массива А по очередям (по “карманам”) выполняется операция конкатенации всех списков в один список.)

4) k = k +1. Выполняем пункты 2, 3 пока (k ≤ p), то есть до старшей значащей цифры числа.

(При k =1 помещаем каждое сортируемое число а _i в очередь с номером (а _i mod r). При k =2 число помещается в очередь с номером , то есть номер очереди равен наибольшему целому числу, равному или меньшему , (другими словами, скобки здесь обозначают операцию взятия целой части числа).)

Процесс поразрядной сортировки для последовательности А =(25, 57, 48, 37, 12, 92, 86, 33) показан в таблице 1 (здесь r =10, p =2, n =8).

Сложность поразрядной сортировки составляет О (n).

Для экономии памяти эффективно использовать линейные связанные списки из указателей для представления сортируемых элементов и очередей.

 

Таблица 1 Пример поразрядной сортировки (LSD)

Очереди для k=1	Очереди для k=2
Разряд	Содержимое разряда	Разряд	Содержимое разряда
	12 92
			33 37
	57 37
Восстанавливаем массив А {12, 92, 33, 25, 86, 57, 37, 48}	Восстанавливаем массив А {12, 25, 33, 37, 48, 57, 86, 92}

Чтобы увидеть, почему этот алгоритм работает правильно, достаточно заметить, что когда числа помещаются в одну очередь (в один “карманам”), например числа 33 и 37 в карман 3, то они будут располагаться в возрастающем порядке, поскольку в списке {12, 92, 33, 25, 86, 57, 37, 48} они упорядочены по самой правой цифре (k =1). Следовательно, в любом “кармане” числа также будут упорядочены по самой правой цифре. И, конечно, распределение чисел на втором этапе по “карманам” в соответствии с первой цифрой (k =2 в примере) гарантирует, что в объединенном списке все числа будут расставлены в возрастающем порядке.

1. Количество присваиваний при формировании очередей для k=1 равно Пр=n=8.

2. Количество присваиваний при восстановлении массива равно r=10, то есть Пр=n+r=18.

3. Количество присваиваний при формировании очередей для k=2 равно n=8, то есть Пр=n+n+n=24.

4. Количество присваиваний при восстановлении массива равно r=10, то есть
Пр = n + r + n + r =(n+r)·p=36.

 

3. Поразрядная сортировка (MSD)

 

MSD (most significant digit radix sort) - поразрядная сортировка сначала по старшей цифре.

Первая часть процесса поразрядной сортировки MSD (- проход по старшей цифре ключа) для последовательности А =(25, 57, 48, 37, 12, 92, 86, 33) показана в
табл. 2 (здесь r =10, p =2, n =8).

 

 

Таблица 2. Пример поразрядной сортировки (MSD)

Очереди для k=1
Разряд	Содержимое разряда
(0)
(1)
(2)
(3)	37 33
(4)
(5)
(6)
(7)
(8)
(9)
Выполнить операцию конкатенации списков. Результат имеет вид: {12, 25, 37, 33, 48, 57, 86, 92}

Массив А практически отсортирован, за исключением двух чисел {37, 33}, которые можно отсортировать любым простым методом сортировки.

Отсортировать числа в разряде 3 с помощью, например, сортировки простым выбором.

Подсчет количества операций:

1. Количество присваиваний при формировании очередей для старшего разряда равно Пр=n=8. Массив А имеет вид {12, 25, 37, 33, 48, 57, 86, 92}, то есть неотсортированы числа в третьем разряде.

2. Количество операций (сравнений и присваиваний) при сортировке, например, простым выбором подмассива (37, 33) равно – сравнений 1, обменов 1 (то есть присваиваний 1*3=3). Всего операций (сравнений и присваиваний) – 1+3=4.

Всего операций при поразрядной сортировке MSD массива А=(25, 57, 48, 37, 12, 92, 86, 33) равно Пр=8+4=12.