Слияние

Сортировка слиянием фон Неймана

Метод Шелла

Сортировка выбором

На этот раз при просмотре массива мы будем искать наименьший элемент, сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив.

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале устранить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

Сортировка слиянием реализуется рекурсивной процедурой, которая получает два параметра l и r - номера начального и конечного элемента в сортируемой части массива.

Сначала разделим массив пополам, отсортируем обе половины с помощью рекурсивного вызова, а затем выполним слияние отсортированных половин в один массив

Подробнее рассмотрим процедуру слияния двух упорядоченных частей массива.

Идея алгоритма состоит в следующем.

Сначала анализируются первые элементы обоих частей. Меньший элемент переписывается в новый массив. Оставшийся элемент сравнивается с элементами из другой части. В новый массив после каждого сравнения попадает меньший элемент.

Процесс продолжается до исчерпания элементов одной из частей. Затем остаток другой части дописывается в новый массив.

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

Процедура слияния

procedure Merge(var a: DataSet; p,q,r: integer);

var

i,j,k:integer;

begin

i:=p; j:=q+1; k:=p;

{i-индекс первой части, j-индекс второй части,

k-индекс результирующего массива}

while (i<=q) and (j<=r) do {пока есть элементы}

if a[i].key<=a[j].key then

begin {переписываем элементы из первой части}

b[k]:=a[i]; inc(i); inc(k);

end

else {переписываем элементы из второй части}

begin

b[k]:=a[j]; inc(j); inc(k);

end;

while i<=q do {если есть элементы в первой части}

begin {переписываем их в результирующий массив}

b[k]:=a[i]; inc(i); inc(k);

end;

while j<=r do {если есть элементы во второй части}

begin {переписываем их в результирующий массив}

b[k]:=a[j]; inc(j); inc(k);

end;

for i:=p to r do a[i]:=b[i]

end;

Соотношение T(n) = 2*T(n/2) + n. Сложность Ө(n log n).

Достоинства – скорость, устойчивость.

Недостаток – требуется дополнительный массив.

Быстрая сортировка Хоара (1960 г.)

Этот метод, называемый также быстрой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).

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

Суть алгоритма: число операций обмена элементов значительно сократится, если менять местами далеко стоящие друг от друга элементы.

Для этого выбирается для сравнения один элемент X (опорный элемент), отыскивается слева первый элемент, который не меньше X, а справа - первый элемент, который не больше X. Найденные элементы меняются местами. Далее процесс продолжается, пока не пройден весь массив.

После первого же прохода все элементы, которые меньше X, будут стоять слева от X, а все элементы, которые больше X, - справа от X. Далее сортируем левую и правую половину рекурсивно.

Процедура QSORT (Вирт)

Procedure QuickSort(var a: DataSet;l,r: integer);

Var

i,j:integer;x,y:Data;

begin

i:=l; j:=r; x:=a[(l+r) DIV 2]; {опорный - средний элемент}

repeat

{ищем слева не меньший опорного}

while a[i].key<x.key do i:=i+1;

{ищем справа не больший опорного}

while x.key<a[j].key do j:=j-1;

if i<=j then