Подразделы

Другие разделы

Дата и время

01/04/2025 05:53:17

Авторизация

Пространственно-временной компромисс

Идея пространственно-временного компромисса Массив частичных сумм Сортировка подсчетом Хеширование Вычисление биномиальных коэффициентов Задача о рюкзаке

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

Если значения элементов представляют собой целые числа в границах от $l$ (нижняя граница) до $u$ (верхняя граница), то мы можем вычислить количество появления каждого из этих значений и сохранить их в массиве $C[0...u-l]$ . Затем первые $C[0]$ позиций в отсортированном списке должны быть заполнены значением $l$ , следующие $C[1]$ позиций — значением $l+1$ , и так далее.

Если кроме ключа в массиве $A$ хранится еще какая-то информация, то результат лучше записывать в новый массив $B[0...n-1]$ . Те элементы $A$ , чьи значения ключей равны наименьшему возможному значению $l$ , копируются в первые $C[0]$ элементов $B$ , т.е. в позиции от 0 до $C[0]-1$ , элементы со значением ключа $l + 1$ — в позиции от $C[0]$ до $(C[0] + C[1])-1$ , и т.д.

Алгоритм CountingSort( $A, l, u$ )
// Входные данные: Массив $A[0...n-1]$ целых чисел от $l$ до $u$
// Выходные данные: Массив $B[0...n-1]$ элементов $A$
// отсортированных в неубывающем порядке
for $i in [0...u-l]$ do
$quad C[i] larr 0$
for $i in [0...n-1]$ do
$quad C[A[i]-l] larr C[A[i]-l]+1$
$S larr "PartialSum"(C)$
for $i in [n-1...0]$ do
$quad j larr A[i]-l$
$quad S[j] larr S[j]-1$
$quad B[S[j]] larr A[i]$
return $B$

Этот алгоритм линеен, поскольку выполняет два последовательных прохода по входному массиву $A$ и по диапазону от $l$ до $u$ .

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

Поразрядная сортировка

Если диапазон значений большой, то можно разбить ключ на отдельные байты и применить сортировку подсчетом ко всем байтам ключа, начиная с самого младшего (LSB). Так как сортировка подсчетом устойчива, то порядок значений в младших байтах сохранится после сортировки по старшему байту, и массив будет упорядочен по значению всего ключа.

Алгоритм RadixSort( $A$ )
// Входные данные: Массив $A[0...n-1]$ целых беззнаковых чисел
// Выходные данные: Массив $A[0...n-1]$ ,
// отсортированный в неубывающем порядке
for $i in [0..."количество байт"-1]$
$quad B larr "CountingSort"(A " где ключ " i"-й байт" , 0, 255)$
$quad A larr B$

Время работы алгоритма $O(n*w)$ , где $w$ - количество байт в ключе. Для $w=4$ (32-битные числа) поразрядная сортировка работает быстрее для $n>500$ , чем быстрая сортировка. Если требуется отсортировать числа со знаком, то можно инвертировать знаковый бит перед сортировкой, а затем инвертировать его обратно.

Если в качестве ключа используются строки переменной длины, то поразрядную сортировку можно выполнять, начиная со старшего байта (MSB), рекурсивно сортируя наборы строк, в которых старшие байты совпали:

Алгоритм StringRadixSort $(b, A, l, r)$
// Входные данные: Номер байта строки $b$
// Подмассив $A[l...r]$ массива строк $A[0...n - 1]$ ,
// определяемый начальным и конечным индексами $l$ и $r$
// Выходные данные: Подмассив $A[l...r]$ , отсортированный
// в неубывающем порядке
Заполнить массив $C[0...255]$ нулями
for $i in [l...r]$
$quad C[A[i][b]] larr C[A[i][b]]+1$
$S larr "PartialSum"(C)$
for $i in [r...l]$
$quad j larr A[i][b]$
$quad S[j] larr S[j]-1$
$quad B[S[j]] larr A[i]$
Копировать $B[0...r-l]$ в массив $A[l...r]$
$l larr l+C[0]$ // пропускаем закончившиеся строки с '\0' в конце
for $i in [1...255]$
$quad$ if $C[i]>1$
$quad quad quad "StringRadixSort"(b+1,A, l, l+C[i]-1)$
$quad l larr l+C[i]$

Для этого варианта алгоритма требуется $O(n+256*w)$ дополнительной памяти и $O(n*w)$ времени в худшем случае, где $w$ – максимальная длина строки.