Анализ алгоритма сортировки слиянием

Оценим время работы функции _mergeSort(). Оно складывается из времени выполнения двух рекурсивных вызовов, слияния и копирования данных из одного массива в другой. Слияние и копирование выполняется за Θ(n), таким образом, имеем рекуррентное соотношение:

Как показано, например, в [9], решением такого рекуррентного соотношения будет T(n)=Θ(n×logn).

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

Быстрая сортировка Хоара

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

 

5

3

8

5

7

1

4

6

2

2

3

4

1

7

5

8

6

5

£

 

Рис. 4.10. Основная идея алгоритма быстрой сортировки

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

Для получения такого разбиения можно действовать следующим образом. Пусть дан массив a[p..r]. Элемент x=a[p] выбирается в качестве граничного (опорного). Нам нужно добиться, чтобы для некоторого q выполнялось следующие условия:

· элементы a[p..q] не больше x

· элементы a[q+1..r] не меньше x

· p£q<r

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

Разбиение производится следующим образом. Двигаясь от конца массива к началу, найдём элемент £ x. Затем, двигаясь от начала к концу, найдём элемент ³ x. Поменяем эти элементы местами. Будем продолжать действовать таким образом, пока не встретимся где-то внутри массива. Пример выполнения разбиения:

 

Массив и положения индексов	Комментарии
4 7 4 2 3 5 Ià  ßj	Идём навстречу друг другу: сначала - справа нелево, останавливаемся при a[j]£x, затем – слева направо, останавливаемся при a[i]³x
4 7 4 2 3 5 I  j	Меняем местами a[i] и a[j]
3 7 4 2 4 5 Ià    ßj	Снова движемся навстречу друг другу
3 7 4 2 4 5 i j	Меняем местами a[i] и a[j]
3 2 4 7 4 5 iàßj	Снова движемся навстречу друг другу
3 2 4 7 4 5 i   j	Поскольку i£j, разбиение завершено

 

После разбиения массива рекурсивно выполнятся сортировка получившихся частей a[p..q] и a[q+1..r].

Приведём пример реализации алгоритма. Здесь a – исходный массив, l и r – диапазон в нём, который нужно отсортировать.

 

void qsort(int a[], int l, int r)

{ if (l>=r) return;

int i=l-1, j=r+1, x = a[l];

for(;;)

{ do {j--;} while (a[j]>x);

do {i++;} while (a[i]<x);

if (i<j)

{ int tmp = a[i]; a[i] = a[j]; a[j] = tmp;

}

else

{ qsort(a,l,j);

qsort(a,j+1,r);

return;

} 

}

}