5.2. Описание алгоритмов

1. Сортировка простыми вставками

Наш первый алгоритм, алгоритм сортировки методом вставок, предназначен для решения задачи сортировки (sortingproblem), сформулированной выше. Приведем еще раз эту формулировку.

Вход: последовательность из п чисел (a₁, а₂, …,а_п).

Выход: перестановка (изменение порядка) (, а'₂,..., а'_п) входной последова­тельности таким образом, что для ее членов выполняется соотношение.

Рис. 5.1. Сортировка карт методом вставок

Принцип работы метода.

Массив разделяется на две части: отсортированную и не отсортированную. Элементы из несортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной частимассива принимают только один первый элемент, а в качестве не отсортированнойчасти– все остальные элементы.

Таким образом, алгоритм будет состоять из n-1-го прохода (n– размерность массива), каждый из которых будет включать четыре действия:

• Взятие очередного i-го неотсортированного элемента и сохранение его в дополнительной переменной;

• Поиск позиции j в отсортированнойчастимассива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

• Сдвиг элементов массива от i-1-го доj-1-го вправо, чтобы освободить найденную позицию вставки;

• Вставка взятого элемента в найденную j-ю позицию.

Псевдокод сортировки методом вставок представлен ниже под названием Insertion_Sort. На его вход подается массивА [1..n], содержащий последователь­ность изnсортируемых чисел (количество элементов массиваА обозначено в этом коде какlength[A].) Входные числасортируются без использования дополни­тельной памяти: их перестановка производится в пределах массива, и объем используемой при этом дополнительной памяти не превышает некоторую посто­янную величину. По окончании работы алгоритмаInsertion_Sort входной массив содержит отсортированную последовательность:

Insertion_Sort(,4)

1 for j 2 to length{A]

2 do keyA[j]

3. Вставка элементаA[j] в отсортированную последовательность A[1..j-1]

4. ij-l

5. while i > 0 и A[i] > key

6 do A[i + 1]A[i]

7 ii-1

8 A[i + 1] key

2. Сортировка слиянием.

Многие полезные алгоритмы имеют рекурсивную структуру: для решения дан­ной задачи они рекурсивно вызывают сами себя один или несколько раз, чтобы решить вспомогательную задачу, имеющую непосредственное отношение к по­ставленной задаче. Такие алгоритмы зачастую разрабатываются с помощью мето­дадекомпозиции, илиразбиения: сложная задача разбивается на несколько более простых, которые подобны исходной задаче, но имеют меньший объем; далее эти вспомогательные задачи решаются рекурсивным методом, после чего полученные решения комбинируются с целью получить решение исходной задачи.

Парадигма, лежащая в основе метода декомпозиции "разделяй и властвуй", на каждом уровне рекурсии включает в себя три этапа.

Разделениезадачи на несколько подзадач.

Покорение — рекурсивное решение этих подзадач. Когда объем подзадачи доста­точно мал, выделенные подзадачи решаются непосредственно.

Комбинирование решения исходной задачи из решений вспомогательных задач.

Алгоритм сортировки слиянием (mergesort) в большой степени соответствует парадигме метода разбиения. На интуитивном уровне его работу можно описать таким образом.

Разделение: сортируемая последовательность, состоящая изп элементов, разби­вается на две меньшие последовательности, каждая из которых содержит п/2 элементов.

Покорение: сортировка обеих вспомогательных последовательностей методом слияния.

Комбинирование: слияние двух отсортированных последовательностей для по­лучения окончательного результата.

Рекурсия достигает своего нижнего предела, когда длина сортируемой последова­тельности становится равной 1. В этом случае вся работа уже сделана, поскольку любую такую последовательность можно считать упорядоченной.

Основная операция, которая производится в процессе сортировки по методу слияний, — это объединение двух отсортированных последовательностей в хо­де комбинирования (последний этап). Это делается с помощью вспомогательной процедуры MERGE(A,p,q,r), гдеА — массив, а р,q и г — индексы, нумерую­щие элементы массива, такие, что рq < т. В этой процедуре предполагается, что элементы подмассивовА[p,..q] иA [q + l,.r] упорядочены. Онасливает эти два подмассива в один отсортированный, элементы которого заменяют текущие элементы подмассиваА[p,..r].

Принцип работы метода.

Алгоритм Неймана упорядочивания массива (алгоритм сортировки слияниями) основан на многократных слияниях уже упорядоченных групп элементов массива. Вначале весь массив рассматривается как совокупность упорядоченных групп по одному элементу в каждой. Слиянием соседних групп получаем упорядоченные группы, каждая из которых содержит два элемента (кроме, возможно, последней группы которой не нашлось парной). Далее, упорядоченные группы укрупняются тем же способом и т.д.

Алгоритм дает хорошие показатели по скорости работы, даже в сравнении с сортировкой методом бинарных деревьев. Единственный недостаток - необходимость использовать дополнительный массив того же размера.

Процедура MERGE_SORT(A,p, г) выполняет сор­тировку элементов в подмассивеA[р..r]. Если справедливо неравенстворr, то в этом подмассиве содержится не более одного элемента, и, таким образом, он отсортирован. В противном случае производится разбиение, в ходе которого вычисляется индексq, разделяющий массивA[р..г] на два подмассива:A[p..q] сэлементами иA [q..r] сэлементами.

MERGE_SORT(A,p,r)

1 if p < r

2 then q

3. MERGE_SORT(A,p, q)

4. MERGE_SORT{A, q+1,r)

5. MERGE(A, p,q,r)

Чтобы отсортировать последовательность А = (А[1],А[2],...,А[п]), вызы­вается процедураMerge_Sort(A, 1,length [А]), гдеlength [А] = п. На рис. 5.2 проиллюстрирована работа этой процедуры в восходящем направлении, еслип — это степень двойки.

Теперь процедуру MERGE можно использовать в качестве подпрограммы в алгоритме сортировки слиянием.

MERGE(A,p,q,r)

1. n q- p + 1

2. n₂ r- q

3 Создаем массивы L[1..n₁ + 1] иR[1..n₂+ 1]

4 for i 1 to n₁

5 do L[i] A[p+ i-1]

6 for j 1 to n₂

7 do R[j] A[q +j]

8. L[n₁ + 1] ∞

9. R[n₂ + 1] ∞

10. i 1

11. j1

12. for к p to r

13do if L[i]

14 then A[k] L[i]

15 i i + 1

16 else A[k] R[j]

17 jj+ 1

Рис. 5.2. Сортировка методом слияния.