Методы программирования. Громов Ю.Ю - 72 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

72
помещаем больший из подфайлов и начинаем обрабатываться оставший-
ся, и так до тех пор, пока не придём к тривиально коротким файлам. Та-
кая процедура гарантирует, что в стеке никогда не будет находиться бо-
лее чем примерно log
2
N элементов.
Описанную процедуру сортировки можно назвать обменной сорти-
ровкой с разделением. Ч.Э.Р. Хоар опубликовал её в 1962 г. под названи-
ем «quicksort» (быстрая сортировка), и это соответствует действитель-
ности, так как весь процесс сортировки нашего файла из шестнадцати
записей требует всего сорок восемь сравнений (меньше любого другого
уже встречавшегося метода за исключением бинарных вставок, требую-
щих сорок семь сравнений).
Заметим, что процедура быстрой сортировки посредством разделе-
ний пригодна в основном для больших значений N. Поэтому короткие
подфайлы желательно сортировать особым образом, как это делается в
следующем алгоритме.
Алгоритм Q. (Обменная сортировка с разделением.)
Записи R
1
, …, R
N
переразмещаются на том же месте памяти. После
завершения сортировки их ключи будут упорядочены: K
1
≤ … ≤ K
N
. Ну-
жен вспомогательный стек для хранения не более чем log
2
N элементов.
Этот алгоритм соответствует процедуре «быстрой сортировки», приве-
дённной выше, с небольшими изменениями в целях повышения эфектив-
ности:
а) предполагается
наличие искусственных ключей K
0
= –
∞ и K
N+1
=
= +
∞ таких, что
K
0
≤ K
i
≤ K
N+1
для 1≤ i ≤ N; (48)
б) подфайлы, состоящие из M и менее элементов, сортируются про-
стыми вставками. Следовательно, М ≥ 1 – выбираемый параметр сорти-
ровки;
в) на некоторых стадиях сортировки делается одно или два допол-
нительных сравнения (допускается перекрытие указателей i, j), чтобы
основные циклы сравнения выполнялись настолько быстро, насколько
это возможно;
г) записи с одинаковыми ключами меняются местами, хотя это не
является строго необходимым.
Q1. [Начальная установка.] Очистить стек и выполнить присваива-
ния l ← 1, r ← N.
Q2. [Начало новой стадии.] (Нам хотелось бы отсортировать файл
R
l
, …, R
r
.) Если r – l < M, то перейти к шагу Q8; в противном случае
i ← l, j ← r, K ← K
l
, R ← R
l
.
Q3. [Сравнение K и K
j
.] Если K < K
j
, то j уменьшить на 1 и повторить
этот шаг.

Страницы