Алгоритм на псевдокоде

Цифровая сортировка

DO (j=L, L–1, … , 1)

<инициализация очередей Q>

<расстановка элементов из списка S в очереди Q по j – ой цифре >

<соединение очередей Q в список S >

OD

Цифровой метод может успешно использоваться не только для сортировки чисел, но и для сортировки любой информации, представленной в памяти компьютера. Необходимо лишь рассматривать каждый байт ключа сортировки как цифру, принимающую значения от 0 до 255. Тогда для сортировки потребуется m=256 очередей. Для выделения каждого байта ключа сортировки можно использовать массив Digit, наложенный в памяти компьютера на поле элемента последовательности, по которому происходит сортировка. Приведем более детальный алгоритм цифровой сортировки.

Алгоритм на псевдокоде

Цифровая сортировка

DO (j=L, L-1, … 1)

DO (i=0, 1, … 255)

Q_i.Tail:=@ Q_i.Head

OD

p:=S

DO (p ≠ NIL)

d:=p → Digit[j]

Q_d.Tail → Next:=p

Q_d.Tail:=p

p:=p → Next

OD

p:=@ S

DO (i=0, 1, … 255)

IF (Q_i.Tail ≠ @ Q_i.Head)

p → Next:=Q_i.Head

p:=Q_i.Tail

FI

OD

p → Next:=NIL

OD

Для цифровой сортировки М<const L(m+n). При фиксированных m и L М=O(n) при n → ∞, что значительно быстрее остальных рассмотренных методов. Однако если длина чисел L велика, то метод может проигрывать обычным методам сортировки. Кроме того, Метод применим только, если задача сортировки сводится к задаче упорядочивания чисел, что не всегда возможно.

Метод обеспечивает устойчивую сортировку. Чтобы изменить направление сортировки на обратное, очереди нужно присоединять в обратном порядке.

1. Варианты заданий

1. Разработать процедуру сортировки последовательности целых чисел методом прямого слияния (язык программирования Паскаль или Си). Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в последовательности. Предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.

2. Разработать процедуру цифровой сортировки последовательности целых чисел (язык программирования Паскаль или Си). Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в последовательности. Предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.

3. Сравнить метод прямого слияния и метод цифровой сортировки по количеству сравнений и пересылок для различных последовательностей. Разработать процедуру построения графика зависимости М+С от длины последовательности n.

4. Сравнить трудоемкости методов сортировки последовательностей длины nи методов быстрой сортировки массивов длиныn.результаты оформить в виде таблицы.

5. Экспериментально определить устойчивость и зависимость от начальной отсортированности последовательности методов сортировки последовательностей.

6. Опытным путем определить константы в выражениях оценки для количества сравнений и пересылок в методе прямого слияния и методе цифровой сортировки.

7. Определить длину чисел (количество цифр в записи числа) в последовательности, при которой цифровая сортировка работает медленнее, чем метод Хоара для массива той же длины.