Стр. 80 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
78
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
5.2.2. Быстрая сортировка (Quick Sort)
Алгоритм
1-й шаг. Выберем некоторый ключ (например, первый). Назовем его ГЭ
(главный элемент).
2-й шаг. Все остальные ключи разделим на 2 группы: ключи, меньшие ГЭ и
большие ГЭ.
3-й шаг. Поставим ГЭ между двумя этими группами.
4-й, 5-й шаг. Применим к каждой из групп тот же самый алгоритм.
Независимо от способа выбора ГЭ и от способа формирования подгрупп,
алгоритм
QS
имеет следующий вид.
x
f
x
f+
1
x
f+
2
…………… x
l-
1
x
l
Начало 27 99 0 8 13 64 86 16 7 10 88 25 90
Первый обмен 27 99 0 8 13 64 86 16 7 10 88 25 90
Второй обмен 27 25 0 8 13 64 86 16 7 10 88 99 90
Третий обмен 27 25 0 8 13 10 86 16 7 64 88 99 90
Просмотры 27 25 0 8 13 10 7 16 86 64 88 99 90
встретились
x
f
перемещается 27 25 0 8 13 10 7 16 86 64 88 99 90
на своё место
Разделённая 16 25 0 8 13 10 7 27 86 64 88 99 90
таблица
i
j
i
j
i
j
i
j
i j
i
j
Рис. 64. Разделение ключей на две группы
Для сортировки таблицы (
x
f
,
x
f
+1
, ...,
x
l
)
x
f
используется для разбиения
таблицы на подтаблицы. На рис. 65 показано, как алгоритм использует два
указателя
i
и
j
для просмотра таблицы во время разбиения. В начале цикла
