Обменная сортировка с разделением
Данный метод
является одним из лучших методов внутренней
сортировки и весьма эффективен для больших
таблиц. Целью каждого шага в данном методе
является помещение очередной рассматриваемой
записи на конечную позицию внутри таблицы. Если
поступать таким способом, то все записи,
предшествующие дан-
ной, будут иметь меньший ключ, в то время как все
последующие - больший. При использовании такого
метода таблица всегда делится на две подтаблицы.
Анологичный процесс может быть применен к каждой
из этих подтаблиц и повторяться до тех пор, пока
все записи не будут установлены на их конечные
позиции.
Используются два индекса i и j с
начальными значениями границ таблицы. Сравниваются ключи
K[i] и K[j], и если перестановка не требуется, то
j уменьшается на 1, и процесс
повторяется. В том случае, когда K[i]>=K[j],
записи R[i] и R[j]
меняются местами. Затем этот процесс повторяется
с i, увеличенным на 1, и фиксированным j до тех пор,
пока не возникает другая перестановка. В этот
момент j снова будет уменьшено на 1, а i останется
фиксированным, и т.д. Процесс выполняется до тех
пор, пока i<j.
Каждый раз таблица разбивается на две
подтаблицы, одна из которых обрабатывается, в то время
как границы второй запоминаются с
тем, чтобы она была обработана позже. В этих
целях может быть использован стек,
представляющий собой матрицу из двух столбцов. В
первом столбце хранятся нижние границы
разделяемых подтаблиц, во втором - верхние
границы. Всякий раз одна из полученных в
результате разделения подтаблиц подвергается
дальнейшему разделению, а границы другой
помещаются в свободную строку стека (обычно в
стек помещаются границы большей по длине таблицы,
поскольку это уменьшает требуемый размер стека).
Как только завершается процесс разделения
текущей подтаблицы, т.е. ее длина станет меньше
трех, для разделения берется подтаблица, границы
которой были занесены в стек последними. Строка
стека, в которой хранились эти границы,
освобождается. Процесс упорядочения завершается,
когда стек полностью освобождается.
Разделение следует применять для
подтаблиц, длина которых больше 9, а короткие
подтаюлицы упорядочивать методом вставки.
Стек занимает мало места.Например,стек из 20 строк
позволяет упорядочить таблицу,содержащую до 10**7
записей.Кроме того, в современных языках
программирования при работе
рекурсивных программ занесение и извлечение из
стека выполняется автоматически,поэтому
рекомендуется использовать именно этот
механизм. Среднее число сравнений для данного
алгоритма составляет n*log(n)
где n - число записей в сортируемой таблице, m -
размер подтаблицы, сортируемой методом вставки.
Наихудшей ситуацией при использовании
рассмотренного алгоритма является случай, когда
таблица уже отсортирована. При этом число
сравнений порядка n , т.е. алгоритм не лучше
сортировки выборкой.
В качестве примера рассмотрим записи со
следующими ключами:
42 23 74 11
36 58 94
Ниже приведена последовательность перестановок
при перемещении записи с ключем 42 на
его конечную позицию. Подчеркнуты ключи,значения
которых сравнивались.
42 23 74 11
36 58 94
~~~ ~~~
42 23 74 11
36 58 94
~~~ ~~~
42 23 74 11
36 58 94
~~~ ~~~
-----------------------------------
36 23 74 11
42 58 94
~~~ ~~~
36 23 74 11
42 58 94
~~~ ~~~
-----------------------------------
36 23 42 11
74 58 94
~~~
~~~
----------------------------------
36 23 11 42
74 58 94
~~
В результате записи с исходными
ключами разбиты на две подтаблицы,а именно,на
наборы [36,23,11] и [74,58,94],к которым применяется тот же
метод.
В качестве разделяющего можно выбрать X - любой
элемент таблицы,например,средний (l=n/2).Сначала
таблица рассматривается слева от X до тех пор,пока
не обнаружится ключ K[i]>X (K[i]<=X, i:=i+1; если K[i]>X,то
i фиксируется). Затем таблица просматривается
справа,пока выполняется K[j]>=X (j:= j-1; если K[j]<X,
то j фиксируется).Элементы таблицы с ключами K[i] и
K[j] меняются местами.Процесс просмотра и
обмена продолжается до тех пор, пока оба просмотра
не встретятся в некоторой позиции таблицы. При
этом необходимо сравнивать индексы i и j
с индексом выбранного элемента X ( индекс
l) с тем,чтобы процесс обмена (перестановки)
записей с ключами K[i] и K[j] выполнялся правильно. В
результате таблица окажется разбитой на левую
часть с ключами меньше или равными X, и правую - с
ключами больше X.
Для каждой из полученных частей процесс
повторяется.
Содержание
|
