Лекции - Структуры и алгоритмы компьютерной обработки данных / 5.Сортировка слиянием. Быстрая сортировка Хоара
..docСортировка слиянием фон Неймана
Сортировка слиянием реализуется рекурсивной процедурой, которая получает два параметра 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 г.)
Суть алгоритма: число операций обмена элементов значительно сократится, если менять местами далеко стоящие друг от друга элементы.
Для этого выбирается для сравнения один элемент 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
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y; {меняем местами}
i:=i+1; j:=j-1;
end;
until i>j; {выполняем пока указатели не встретятся}
if l<j then quicksort(l,j); {сортируем левую половину}
if i<r then quicksort(i,r); {сортируем правую половину}
end;
Сложность QSORT
Один проход алгоритма имеет сложность Ө(n).
В лучшем случае, если на каждом шаге опорные элементы делят массив на две равные половины, сложность алгоритма будет Ө(n log n).
В худшем случае, если опорные элементы будут иметь наименьшие или наибольшие ключи, на каждом проходе число отсортированных элементов будет уменьшаться на 1, понадобится (n-1) проход, и сложность будет Ө(n2).
Можно доказать, что в среднем сложность быстрой сортировки Ө(n logn)
Улучшения алгоритма
-
Использование простого алгоритма (вставками) для небольших частей массива (до 10 элементов).
procedure QuickSort (l,t:integer);
var i:integer;
begin
if t-l>m then
begin
i:=part(l,t); QuickSort (l,i-1); QuickSort (i+1,t);
end
Else Insertion(l,t);
end;
-
Выбор в качестве опорного случайного элемента, либо медианы из трех: первого, последнего и среднего.
x := a[ l + random (r – l + 1) ]