Стр. 81 - Основы алгоритмов и структур данных

Содержание 79
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
“while i < j” i и j указывают соответственно на первое и последнее имена, о
которых известно то, что они находятся не в тех частях файла, в которых
требуется. Когда i и j встречаются, то есть когда i>=j, все имена находятся в
соответствующих частях таблицы и хf помешается между двумя частями,
меняясь при этом местами с x j. Алгоритм предполагает, что имя xl+1 определено
и больше, чем хf , xf+1, ..., xl .
//х – массив, i,j – верхний и нижний индексы сортируемой группы
QuickSort(x, i, j)
{
if (i>=j) return;
S = <выбор главного элемента>
<x1 меняем с xs>
/* разделить элементы массива х, начиная с i+1 по j, а
индекс последнего элемента 1-й группы записать в s */
Separate(x, i, j, s);
<xi меняем с xs>
QuickSort(x, i, s-1);
QuickSort(x, s+1, j);
}
Вызов: QuickSort(х, 1, N);
Выбор Главного Элемента
Быстрая сортировка будет работать эффективнее, если при делении
получаются примерно равные по размеру подгруппы. Потому было бы
идеально, чтобы ГЭ был средним в текущем подмассиве. Чаще всего в качестве
ГЭ выбирают ни больший и ни меньший из хi, xj и x(i+j) /2. Также эффективно
выбирать ГЭ с помощью генератора случайных чисел.
Процедура разделения
Separate (x, u, v , s) // главный элемент в позиции u.
Просматриваются ключи одновременно сверху вниз с (u+1) позиции и
снизу вверх с v позиции. Каждый раз, когда ключ сверху больше ГЭ, а снизу
меньше ГЭ, меняем их местами.