Рекурсивный алгоритм сортировки слиянием
1. Если Правая_граница = 0, то
Результат = 0
Иначе
1.1. Если Правая_граница = 1, то
Результат = А0
Иначе
1.1.1.Если Правая_граница = 2, то
Если А1 < А0
Результат = А1, А0
Иначе
Результат = А0, А1
1.1.2.Иначе
a) Упорядочить первую половину массива А:
Вызвать Сортировку(А; Левая_граница; Правая_граница/2);
b) Упорядочить вторую половину массива А:
Вызвать Сортировку (А; Левая_гр +Правая_гр/2+1; Правая_гр);
c) Слияние Первой и Второй половин массива А:
Слияние A[0… Левая_гр + Правая_гр/2] и
A[Левая_гр + Правая_гр/2 + 1; Правая_гр]
2. Вывести массив А.
3. Закончить.
Алгоритм 6. Сортировка Боуза- Нельсона
Этот метод реализует один из способов слияния. Он удобен для сортировки больших массивов, находящихся на устройствах последовательного доступа (например, винчестерах). Массив А разбивается на две половины: B и С. Эти половины сливаются в упорядоченные пары, объединяя первые элементы из B и С в первую пару, вторые – во вторую и т.д. Полученному массиву присваивается имя А, после чего операция повторяется. При этом пары сливаются в упорядоченные четверки. Предыдущие шаги повторяются: четверки сливаются в восьмерки и т.д., пока не будет упорядочен весь массив, т.к. длины частей каждый раз удваиваются. Если размер массива нечетный, или на некотором шаге получатся неполные части, то выполняют отдельно слияние начал, концов и центральной частей. Описанный алгоритм можно проиллюстрировать следующим примером.
Пример. Исходная последовательность
А = 44 55 12 42 94 18 06 67
Шаг 1
Первая половина B = 44 55 12 42
Вторая половина С = 94 18 06 67
А = 44 94 18 55 06 12 42 67 – для наглядности нечетные пары выделены.
Шаг 2
Первая половина B = 44 94 18 55
Вторая половина С =06 12 42 67
А = 06 12 44 94 18 42 55 67 – выделены упорядоченные четверки.
Шаг 3
Первая половина B = 06 12 44 94
Вторая половина С = 18 42 55 67
А = 06 12 18 42 44 55 67 94 – отсортированный массив.
Судя по описанию, алгоритм проще всего реализовать с помощью рекурсии, причем, в отличие от традиционной сортировки слиянием он не требует дополнительной памяти. Обозначим 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.
3. Вывести массив А.
4. Закончить.
Число сравнений и пересылок при реализации сортировки методом Боуза - Нельсона в самом худшем случае пропорционально n log n, т.е. сложность алгоритма O(n log n). Дополнительная память не требуется.
Алгоритм 7. Быстрая сортировка
Метод использует тот факт, что число перестановок в массиве может резко сократиться, если менять местами элементы, находящиеся на большом расстоянии. Он реализует метод «разделяй и властвуй». Для этого обычно в середине массива выбирается один элемент (опорный). Далее слева от опорного располагают все элементы, меньше его, а справа – больше. Затем тот же прием применяют к половинкам массива. Процесс заканчивается, когда в частях массива останется по одному элементу.
В алгоритме используются два разнонаправленных процесса. Первый выполняется от начала массива и ищет элемент, больший опорного. Второй - работает с конца и ищет элемент, меньший опорного. Как только такие элементы найдены, производится их обмен местами. Далее поиск продолжается с того места, где процессы остановились.
Таким образом, когда процессы встречаются, любой элемент в первой части меньше любого во второй. Это значит, что их уже сравнивать друг с другом не придется. Остается только провести такую же операцию по отношению к полученным половинам, и так далее, пока в очередной части массива не останется один элемент. Это будет означать, что массив отсортирован. Очевидно, что наиболее удобный способ реализации рассмотренного метода – рекурсивный.
Общий алгоритм можно представить так.
1. Из массива выбирается некоторый опорный элемент, Опорный = a[i], i=n/2.
2. Запускается процедура разделения массива, которая перемещает все элементы, меньшие, либо равные Опорному, влево от него, а все, большие, равные Опорному, - вправо.
3. Теперь массив состоит из двух подмассивов, причем длина левого меньше, либо равна длине правого.
4. Для обоих подмассивов, если в них больше двух элементов, рекурсивно заполняется та же процедура.
В конце получится полностью отсортированная последовательность.