Уточненный рекурсивный алгоритм процедуры быстрой сортировки
Исходные данные: Массив А; Левая_граница (0); Правая_граница (n-1)
1. Индекс в начале, i = Левая_граница.
2. Индекс в конце, j =Правая_граница.
3. Опорный = A[(Левая_граница + Правая_граница) / 2].
4. Повторять
4.1. Движение слева направо:
Пока A[i] < Опорный
i = i + 1
4.2. Движение справа налево:
Пока A[j] > Опорный
j = j - 1.
4.3. Поменять местами A[i] и A[j].
4.4. i = i + 1.
4.5. j = j - 1.
Пока Левая_граница < Правая_граница.
5. Если Левая_граница < j, то отсортировать А от Левая_граница до j,
6. Если i > Правая_граница, то отсортировать А от i до Правая_граница.
7. Вывести массив А.
Сложность алгоритма зависит от выбора опорного элемента. Наилучшим считается значение так называемой медианы. Это – элемент, который меньше или равен половине элементов массива и больше или равен другой половине. Нахождение такого элемента требует выполнения дополнительных операций.
Число сравнений и пересылок при реализации быстрой сортировки в худшем случае пропорционально n2, т.е. его временная сложность равна О(n2), а в среднем и лучшем - О(n log n). Вообще рассмотренный метод является одним из наиболее эффективных, о чем говорит его название. Причем, наилучшие характеристики он обеспечивает для массивов, имеющих случайные значения.
3.4.3. Сортировка Боуза - Нельсона
Главным минусом предыдущих методов является удвоение размера памяти, первоначально занятой сортируемыми данными. Алгоритм Боуза – Нельсона является рекурсивным и не требует дополнительной памяти, т.е. упорядочение выполняется на месте исходного массива. Он основан на простой идее: слить две равные по размеру упорядоченные части можно слиянием их начальных, конечных половин, а также слиянием середин (2-й половины 1-го результата с 1-й половиной 2-го результата). Эта процедура иллюстрируется рисунком.
Если части не равны или не делятся точно пополам, процедуру уточняют соответствующим образом. Аналогично слияние «половинок» можно свести к слиянию «четвертушек», «восьмушек» и т. д. Таким образом, становится очевидной необходимость использования рекурсии.
 |
Рисунок. Иллюстрация слияния частей двух серий
Обозначим r - расстояние между началами сливаемых частей, m - их размер и j - наименьший номер элемента. Будем считать, что выполняется сортировка по возрастанию.
Рекурсивный алгоритм сортировки Боуза- Нельсона
1. Слияние
1.1. Начало рекурсии. Если j+r ≤ n, то
1.1.1. Если m = 1, то
a) Если A[j] > A[j+r], то
Поменять местами A[i] и A[j+r].
1.2. Иначе
1.2.1. m = m / 2.
1.2.2. Выполнить Слияние «начал» от j до m с расстоянием r.
1.2.3. Если j+r+m ≤ n, то
Выполнить Слияние «концов» от j+m до m с расстоянием r.
1.2.4. Выполнить Слияние «центральной части» от j+m до m с расстоянием m - r.
2. Основная часть рекурсии
2.1. m = 1.
2.2. Повторять
2.3. Цикл слияния списков равного размера
2.3.1. j = 1.
2.3.2. Пока j+m ≤n
1) Выполнить Слияние (j,m,m);
2) j = j + 2m
2.3.3. Удвоение размера списка перед началом нового прохода
m = 2m.
Конец цикла 2.2, реализующего все слияния
Пока m < n.
Число сравнений и пересылок при реализации сортировки методом Боуза - Нельсона в самом худшем случае пропорционально n log n, т.е. сложность алгоритма O(n log n). Дополнительная память, как уже отмечалось, не требуется.