Таблица 2

БЫСТРАЯ СОРТИРОВКА

{1,г) Стек

Алгоритм Q (Быстрая сортировка). Записи Ri,...,Rn перекомпоновываются в пределах того же пространства памяти. По завершении сортировки их ключи будут упорядочены: Ki < < К- Нужен вспомогательный стек для хранения не более чем [IgiVj элементов. Этот алгоритм (рис. 19) соответствует описанной выше процедуре быстрой сортировки посредством разделений с небольшими изменениями с целью повышения эффективности.

a) Предполагается наличие искусственных ключей Kq = -оо и K+i = +оо, таких, что

Ko<Ki< Kn+1 для 1 < j < iV. (13)

(Равенство допускается.)

b) Подмассивы, состоящие из М и менее элементов, являются нерассортирован-ными слева до самого конца выполнения процедуры. Затем выполняется единственный проход сортировки методом простых вставок, где М > 1 - параметр, который, выбирается, как описано ниже. (Эта идея принадлежит Р. Седгевику и позволяет сэкономить на вспомогательных операциях, которые необходимы, если непосредственно использовать метод прямых вставок по отношению к коротким подмассивам.)

c) Записи с одинаковыми ключами меняются местами, хотя это не является строго необходимым. (Эта идея, принадлежащая Р. К. Синглтону (R. С. Singleton), способствует разделению подмассивов почти пополам, если имеются равные ключи; см. упр. 18.)

Q1. [Начальная установка.] Если N < М, перейти к шагу Q9. В противном случае очистить стек и установить / +- 1, г +- iV.

Q2. [Начать новую итерацию.] (Необходимо рассортировать подмассив Л;... Лг- Из самого существа алгоритма вытекает, что г > I + М и Ki-\ < Ki < Kr+i при I < i < г.) Установить i<r-l, j<r-r + luK Ki. (Обсуждение наилучшего выбора К приведено ниже.)

Ql. Начальная установка

. Сравнить\ v/Q4. Cpaci Ki-.K /-\ K:Kj

Q2. Начать новую итерацию

N<M

Q9. Сортировка методом простых вставок

Стек пуст

Q6. Взаимный обмен

у < / Q5. ПроверитьЧ

Q8. Извлечь из стека

Длина обоих

Q7. Поместить в стек

подмассивов <.М

Рис. 19. Обменная сортировка с разделением (быстрая сортировка).

Q3. [Сравнить Ki.K] (В этот момент массив перекомпонован таким образом, что

Kk<K для / - 1 < А; < г, К < Kk для j < А; < г + 1 (14)

и / < г < j.) Увеличить i на 1; затем, если Ki < К, повторить этот шаг. (Как только Kj > К, итерацию нужно прекратить, сохранив г < j.)

Q4. [Сравнить K:Kj.] Уменьшить j на 1; затем, если К < Kj, повторить этот шаг. (Как только К > ivj-i, итерацию нужно прекратить, сохранив j > г - 1.)

Q5. [Проверить (В этот момент соблюдается условие (14), кроме случая, когда к = i ш к = j; также Ki>K>Kjnr>j>i - 1>1.) Если j < i, переслать Ri Rj и перейти к шагу Q7.

Q6. [Взаимный обмен.] Вьшолнить взаимный обмен Ri f+ Rj и вернуться к шагу Q3.

Q7. [Поместить в стек.] (Теперь подмассив Ri.. .Rj .. .Rr разделен так, что Kk < Kj при I - 1 < к < j и Kj < Kk при j < А; < г + 1.) Если г - j > j - I > М, то поместить в стек {j + l,r), установить г j - 1 и перейти к шагу Q2. Если j - I > г - j > Л/, то поместить в стек - установить I j + 1 и перейти к шагу Q2. (Каждый элемент в стеке - пара (а, Ь) - это запрос на сортировку подмассива Ra...Rb, которую нужно будет выполнить позже.) В противном случае, если r-j>M>j-l, установить I j + 1 и перейти к шагу Q2 или, если j - 1>М>г-j, установить г j - 1 и перейти к шагу Q2.

Q8. [Извлечь из стека.] Если стек не пуст, извлечь верхний элемент стека {l,r), установить / f- /, г г и возвратиться к шагу Q2.

Q9. [Сортировка методом простых вставок.] Для j = 2, 3, ..., N, если Kji > Kj, выполнять следующие операции: установить сначала К <- Kj, R Rj, г j - 1, а затем - Ri+i <r-RiUi<r-i - I один или более раз до тех пор, пока не выполнится условие Ki < К. Далее установить Ri+i <г- R. (Это, по существу, алгоритм 5.2.IS, модифицированный в соответствии с идеей упр. 5.2.1-10 и ответом к упр. 5.2.1-33. Шаг Q9 можно опустить, если М = 1. Предупреждение. Последняя стадия - сортировка методом простых вставок - может скрыть ошибки на шагах Q1-Q8, поэтому учтите, что программу, реализующую

этот алгоритм, следует тщательно проверить, не особо доверяя тому факту, что получен правильный результат!)

Соответствующая MIX-программа довольно велика, но не сложна. На самом деле большая часть команд относится к шагу Q7, на котором проводятся совершенно очевидные манипуляции переменными.

Программа Q {Обменная сортировка с разделением). Записи, которые предстоит рассортировать, находятся в ячейках от INPUT+1 до INPUT+N. Предполагается, что в ячейках INPUT и INPUT+N+1 содержатся значения, соответственно минимальное и максимальное для разрядной сетки компьютера MIX. Стек располагается в ячейках STACK+1, STACK+2, ...; точное число ячеек, которые необходимо отвести под стек, обсуждается в упр. 20. Значения регистров: г12 = Z, г13 = г, г14 = г, г15 = j, rI6 = размер стека, тА = К = R. Полагаем, что N > М.

Первый компонент элемента стека. Второй компонент элемента стека. Q1. Начальная установка. Очистить стек. /+- 1. r<-N.

02. Начать новую итерацию, j г + 1. К Ki.

Перейти к шаху Q3, опустив "г ч- г -f-1". Q6. Взаимный обмен.

Ri <-> Rj.

03. Сравнить Kj

Повторить, если К > Ki. Q4. Сравнить К : Kj. j

4- j ~ 1.

Повторить, если К < Kj. 0.5. Проверить i:

Перейти к шагу Q6, если j > i.

Ri +- Rj. Rj +- R.

07. Поместить в стек. rI4 i- г - j - М.

illi- j -I- M.

Переход, если г - j > j - I. Перейти к шагу Q8, если M>j~l>r - j. Переход, если j - l>M>r- j. (Сейчас j - I > г - j > М.)