Рекурсивный алгоритм сортировки слиянием

1. Если Правая_граница = 0, то

Результат = 0

Иначе

1.1. Если Правая_граница = 1, то

Результат = А₀

Иначе

1.1.1.Если Правая_граница = 2, то

Если А₁ < А₀

Результат = А₁, А₀

Иначе

Результат = А₀, А₁

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 + 2 m

2.3.3. Удвоение размера списка перед началом нового прохода

m = 2 m.

Конец цикла 2.2, реализующего все слияния

Пока m < n.

3. Вывести массив А.

4. Закончить.

Число сравнений и пересылок при реализации сортировки методом Боуза - Нельсона в самом худшем случае пропорционально n log n, т.е. сложность алгоритма O(n log n). Дополнительная память не требуется.

 

Алгоритм 7. Быстрая сортировка

 

Метод использует тот факт, что число перестановок в массиве может резко сократиться, если менять местами элементы, находящиеся на большом расстоянии. Он реализует метод «разделяй и властвуй». Для этого обычно в середине массива выбирается один элемент (опорный). Далее слева от опорного располагают все элементы, меньше его, а справа – больше. Затем тот же прием применяют к половинкам массива. Процесс заканчивается, когда в частях массива останется по одному элементу.

В алгоритме используются два разнонаправленных процесса. Первый выполняется от начала массива и ищет элемент, больший опорного. Второй - работает с конца и ищет элемент, меньший опорного. Как только такие элементы найдены, производится их обмен местами. Далее поиск продолжается с того места, где процессы остановились.

Таким образом, когда процессы встречаются, любой элемент в первой части меньше любого во второй. Это значит, что их уже сравнивать друг с другом не придется. Остается только провести такую же операцию по отношению к полученным половинам, и так далее, пока в очередной части массива не останется один элемент. Это будет означать, что массив отсортирован. Очевидно, что наиболее удобный способ реализации рассмотренного метода – рекурсивный.

Общий алгоритм можно представить так.

1. Из массива выбирается некоторый опорный элемент, Опорный = a[i ], i=n /2.

2. Запускается процедура разделения массива, которая перемещает все элементы, меньшие, либо равные Опорному, влево от него, а все, большие, равные Опорному, - вправо.

3. Теперь массив состоит из двух подмассивов, причем длина левого меньше, либо равна длине правого.

4. Для обоих подмассивов, если в них больше двух элементов, рекурсивно заполняется та же процедура.

В конце получится полностью отсортированная последовательность.