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

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

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 велика, то метод может проигрывать обычным методам сортировки. Кроме того, Метод применим только, если задача сортировки сводится к задаче упорядочивания чисел, что не всегда возможно.

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

6.3 Варианты заданий

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

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

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

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

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

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

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

7. Двоичный поиск в упорядоченном массиве

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

Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берём средний элемент отсортированного массива и сравниваем с ключом X. Возможны три варианта:

1. Выбранный элемент равен X. Поиск завершён.

2. Выбранный элемент меньше X. Продолжаем поиск в правой половине массива.

3. Выбранный элемент больше X. Продолжаем поиск в левой половине массива.

Далее рассмотрим две версии реализации двоичного поиска в упорядоченном массиве.

Версия 1

Пример.Найти в отсортированном массиве элемент с ключом X = б.

Рисунок 24 Первая версия поиска