Cхемы сортировки

Список литературы

Структуры данных и алгоритмы. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. – М.: Издательский дом «Вильямс», 2000

Алгоритмы: построение и анализ. Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: МЦНМО, 2000.

Д. Кнут. Искусство программирования для ЭВМ.

Одной из первых крупных систем программного обеспечения, продемонстрировавших богатые возможности сортировки, был компилятор Larc Scientific Compiler, разработанный фирмой Computer Sciences Corporetion в 1960 г. В этом оптимизирующем компиляторе для расширенного ФОРТРАНа сортировка использовалась весьма интенсивно, так что различные алгоритмы компиляции работали с относящимися к ним частям исходной программы, расположенными в удобной последовательности. При первом просмотре осуществлялся лексический анализ, т.е. выделение с исходной программе лексических единиц (лексем), каждая из которых соответствует либо константе, либо оператору и т.д. Каждая лексема получала несколько порядковых номеров. В результате сортировки по именам и соответствующим порядковым номерам все использования данного идентификатора оказывались собранными вместе. "Определяющие вхождения", специализирующие идентификатор как имя функции, параметр или многомерную переменную, получали меньшие номера, поэтому они оказывались первыми в последовательности лексем, отвечающих этому идентификатору. Тем самым облегчалась проверка правильности использования идентификаторов, распределение памяти с учетом деклараций эквивалентности и т.д. Собранная таком образом информация о каждом идентификаторе присоединялась к соответствующей лексеме. Поэтому не было необходимости хранить в оперативной памяти "таблицу символов", содержащую сведения о идентификаторах. После такой обработки лексемы снова сортировались по другому порядковому номеру, где новый порядок лексем использовался на последующих фазах компиляции - для облегчения оптимизации циклов, включение в листинг сообщений об ошибках и т.д.

С читается, что в среднем более 25% машинного времени систематически тратиться на сортировку. Во многих вычислительных системах, например, СУБД, более половины машинного времени. Из этой статистики можно заключить, что либо

1) сортировка имеет много важных применений;

2) ею часто пользуются без нужды;

3) применяются неэффективные медленные алгоритмы сортировки.

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

Простые схемы сортировки

Простая обменная сортировка методом «пузырька»

Листинг. Алгоритм „пузырька"

(1) for i:= 1 to n - 1 do

(2) for j:= 1 downto i + 1 do

(3) if R[j].K < R[j - 1].K then

(4) swap (A[j], A[j-1])

Процедура swap (перестановка) используется во многих алгоритмах сортировки для перестановки записей местами, ее код показан в следующем листинге.

Листинг Процедура swap

procedure swap ( var x, у: recordtype )

{swap меняет местами записи х и у }

var temp : recordtype;

begin

temp:=x;

x:= y,

y:= temp;

end; { swap } ,

Приведенная блок-схема реализует более «интеллектуальный» алгоритм сортировки, в котором запоминается последняя позиция, в которой произошел обмен. Благодаря чему исключаются те просмотры последовательности в позициях превышающих позицию, занятую текущим элементом (т.к. в этих позициях «естественным образом расположились бОльшие ключи).

Сортировка простой вставкой.

П усть 1j N и записи R₁,…,R_j-1 уже размещены так, что К₁  К₂,…К_{j -1}. Будем сравнивать по очереди К_j с К_{j –1}, К_j-2,… до тех пор, пока не обнаружим, что запись R_j следует вставить между R_i и R_i+1; тогда подвинем записи R_i+1 ,…, R_j-1 на одно место вверх и поместим новую запись в позицию i+1. Удобно совмещать операцию сравнения и перемещения.

Алгоритм В (Сортировка простыми вставками).

1. (Цикл по j) Выполнить шаги с В2 по В6 при j = 2, 3,…,N. После чего алгоритм завершить.

2. (Установить i, К, R) Установить i := j –1, К:=К _j , R R_j (R – запись которую мы позиционируем, К – ключ позиционируемой записи, i – номер позиции за которой расположится запись R)

1. (Сравнить К, К_i ) Если К = К_i , то перейти к шагу В6, (т.е. мы нашли искомое место), иначе шаги В4 и В5.

2. (Переместить R_i , вперед) Установить R _i+1 := R _i.

3. (Уменьшить i). Установить i := i –1. Если i  0, то перейти к шагу В4, иначе (т.е. если i =0, то К – наименьший из рассмотренных на данный момент ключей и R надо установить на 1^ю позицию) перейти на шаг В6.

4. (R на место R _i ) Установить R _i+1:= R.

Действие алгоритма приведено на Рис. 1

Рис. 1 Применение простых вставок

Реализация алгоритма для краткости (и общности при сравнении алгоритмов O(N²)) используется процедура Swap. На самом деле, используемое в блок-схеме «полуприсваивание» (сдвиг), значительно уменьшает общее число присваиваний

Листинг 8.3. Сортировка вставками

(1) {R[1].K уже на месте}_;

(2) for i:= 2 to n do

begin

(3) j:= i;

(4) while R[j].K < R[j - 1].K do

begin

(5) swap(R[j], R[j - 1]);

(6) j:= j - 1

end

end

Бинарные вставки.

Когда при сортировке простыми вставками обрабатывается jя запись, ее ключ сравнивается примерно с j/2 ранее отсортированными ключами; поэтому после прохода всех N записей общее число сравнений (1+2+3+…+N) / 2 = ((N+1)*N/2) / 2  N² / 4, а это очень много даже при умеренных значений N.

Для уменьшения числа сравнений можно использовать бинарную вставку. Пусть, например, вставляется 64 запись. Можно сначала сравнить ключ К₆₄ с К₃₂, если он меньше, сравниваем с К₁₆, иначе с К₄₈. Однако, найдя номер позиции, куда надо поместить запись, надо все равно переместить j/2 записей, что высвободить место.

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

Сортировка посредством простого выбора

Идея сортировки посредством выбора в следующем: на i-ом этапе сортировки выбирается запись с наименьшим ключом среди записей R[i], ..., R[п] и меняется местами с записью R[i]. В результате после i-ro этапа все записи R[1], ..., R[i] будут упорядочены. Сортировку посредством выбора можно описать следующим образом:

Листинг 8. Сортировка посредством выбора

var

lowkey : keytype;

{ текущий наименьший ключ,

найденный при проходе

по элементам R[i], ..., R[n] }

lowindex: integer;

{ позиция элемента с ключом lowkey }

begin

(1) for i:= 1 to n - 1 do

begin

(2) lowindex:= i;

(3) lowkey:= R[i].K;

(4) for j:= i + 1 to n do

{ сравнение ключей с текущим ключом lowkey }

(5) if R[j].K < lowkey then

begin

(6) lowkey := R[j].K;

(7) lowindex:= j

end;

(8) swap(R[i], R[lowindex])

end

end;

Для разнообразия блок-схема представлена поиском максимального элемента из еще неотсортированных.

Заметим, что в методе пузырьком производится меньше сравнений, чем при простом выборе, и она, как может показаться, предпочтительнее. Но в действительности "пузырек" в два раза медленнее простого выбора из-за того, что в "пузырьке" производится слишком много обменов, а в простом выборе обменов всего их не более N-1.

Возможно ли усовершенствование алгоритма простого выбора? То есть можно ли находить максимум более быстрым способом? Ответ: НЕТ.

Лемма. В любом алгоритме нахождения максимума из n элементов, основанном на сравнении пары элементов, необходимо выполнить по крайней мере n–1 сравнений.

Доказательство. Если произведено менее n-1 сравнений, то найдутся по крайней мере два элемента (максимальный и нерассмотренный), для которых не было обнаружено ни одного элемента, превосходящего их по величине. Следовательно, мы не узнаем, который из этих двух элементов больше, и, значит, не сможем определить максимум. (конец)

Временная сложность методов сортировки

Методы "пузырька", вставками и посредством выбора имеют временную сложность О(п²) и (n²) на последовательностях из п элементов.

Рассмотрим листинг метода "пузырька". Независимо от того, что подразумевается под типом recordtype, выполнение процедуры swap требует фиксированного времени. Поэтому строки (3), (4) затрачивают с₁ единиц времени; c₁ — некоторая константа. Следовательно, для фиксированного значения i цикл строк (2) - (4) требует не больше с₂(n - i) шагов; с₂ — константа. Последняя константа несколько больше константы с₁, если учитывать операции с индексом j в строке (2). Поэтому вся программа требует

шагов, где слагаемое с₃п учитывает операции с индексом i в строке (1). Последнее выражение не превосходит (с₂/2 + с₃)n² для п > 1, поэтому алгоритм "пузырька" имеет временную сложность О(п²). Нижняя временная граница для алгоритма равна (n²), поскольку если даже не выполнять процедуру swap (например, если список уже отсортирован), то все равно п(п - 1)/2 раз выполняется проверка в строке (3).

Сортировка вставками. Цикл while в строках (4) - (6) выполняется не более O(i) раз, поскольку начальное значение j равноp i, а затем j уменьшается на 1 при каждом выполнении этого цикла. Следовательно, цикл for строк (2) — (6) потребует не более шагов для некоторой константы с. Эта сумма имеет порядок О(п²).

Можно показать, что если список записей первоначально был отсортирован в обратном порядке, то цикл while в строках (4) - (6) выполняется ровно i – 1 раз, поэтому строка (4) выполняется раз. Следовательно, сортировка вставками в самом худшем случае требует времени не менее  (n²). Можно показать, что нижняя граница в среднем будет такой же.

Сортировка посредством выбора, (см. соответствующий листинг). Легко проверить, что внутренний цикл в строках (4) - (7) требует времени порядка О(п - i), поскольку j здесь изменяется от i + 1 до п. Поэтому общее время выполнения алгоритма составляет для некоторой константы с. Эта сумма, равная сп(п - 1)/2, имеет порядок роста О(n²). С другой стороны, нетрудно показать, что строка (4) выполняется не менее раз независимо от начального списка сортируемых элементов. Поэтому сортировка посредством выбора требует, времени не менее  (п²) в худшем случае и в среднем.

Метод Шелла (сортировка с убывающем шагом).

Записи R₁,…, R_N перемещаются на том же месте. После завершения сортировки их ключи будут упорядочены: К₁  … К _N. Для управления процессом сортировки используются вспомогательная последовательность шагов h_t h_t-1,…, h₁, где h₁=1. Правильно выбрав эти приращения, можно значительно сократить время сортировки. При t = 1 алгоритм сводится к алгоритму простой вставки.

1. ( Цикл по р) Выполнить шаг Ш2 при р = t, t –1, …, 1, после чего завершить алгоритм .

2. (Цикл по j). Установить h := h_t, и выполнить шаги Ш3 – Ш6 при h j  N. (для сортировки элементов, отстоящих друг от друга на h позиций, воспользуемся простыми вставками и в результате получим К _t  К _{t + h} при 1 i  N – h.

3. (Установить i, К, R). Установить i = j – h, К=К _j , R = R _j .

4. (Сравнить К, К _i ) Если К=К _i , то перейти к шагу Ш6.

5. (Переместить R_i , уменьшить i). Установить R _{i +h} = R _i , затем i =i–h. Если i  0, то возвратиться к шагу Ш4.

6. (R на место R_i+h) Установить R_i+h = R.

На выбор шагов h_t, h_t-1,…, h₁ значительно влияет условие делимости:

h_s+1 mod h_s = 0, при t > s = 1.