Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагментпрограммы, поясняющий данный алгоритм.

Быстрая сортировка часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении nэлементов), хотя и имеющий ряд недостатков.

Достоинства: быстрота, простота реализации, хорошо сочетается с механизмами кэширования и виртуальной памяти. Требует лишь дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае памяти). Существует эффективная модификация (алгоритм Седжвика) для сортировки строк — сначала сравнение с опорным элементом только по нулевому символу строки, далее применение аналогичной сортировки для «большего» и «меньшего» массивов тоже по нулевому символу, и для «равного» массива по уже первому символу.

Недостатки:

§ Сильно деградирует по скорости (до ) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, используя такие модификации алгоритма, как Introsort, или вероятностно, выбирая опорный элемент случайно, а не фиксированным образом.

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

§ Неустойчив — если требуется устойчивость, приходится расширять ключ.

Эффективность:

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

Оценим эффективность метода быстрой сортировки. На каждом шаге делим массив на две части, для каждой из этих частей – N/2 сравнений (всего – 2*N/2=N), затем на 2-ом шаге снова делим, получаем N/4 сравнений (4*N/4=N) и т.д. Так как глубина рекурсии (количество разбиений) равна Log₂N, а количество сравнений на каждом уровне – N, то сложность алгоритма С = Θ (N*logN).

Принцип действия:

Реализация данного метода сортировки основывается на рекурсивном вызове процедуры упорядочивания. Она была разработана в 1962 году профессором Оксфордского университета К.Хоаром.

Быстрая сортировка основывается на принципе «разделяй и властвуй» и является улучшенной модификацией пузырьковой сортировки. Сначала берется весь массив и частично упорядочивается особенным образом: выбирается серединный элемент, назовем его ключом, а остальные элементы упорядочиваются относительно этого ключа так, чтобы слева располагались элементы меньшие ключа (если массив сортируется по возрастанию), а справа – большие. В итоге ключевой элемент встает на «свое место». Затем к левой и правой частям (относительно ключа) применяется этот же метод, то есть выбирается новый ключ и упорядочивание подмассива относительно его. И так до тех до тех пор, пока каждая из частей не будет содержать ровно один элемент.

Пример:

Рассмотрим работу данного метода на примере сортировки массива А={6, 23, 17, 8, 14, 25, 6, 3, 30, 7} по возрастанию.

Выбирается серединный элемент массива – key=A[5]=14. Просматривая левую часть массива (слева направо) найдем элемент, больший key, а в правой части ищем элемент (двигаясь справа налево), меньший key. Затем эти элементы меняем местами.

(i,j- индексы левой и правой половины соответственно)

i=2 j=10

6 23 17 8 14 25 6 3 30 7

Продолжаем поиск элементов для перестановки:

i=3 j=8

6 7 17 8 14 25 6 3 30 23

i=5j=7

6 7 3 8 14 25 6 17 30 23

i=6 j=7

6 7 3 8 6 25 14 17 30 23

i=j=6

6 7 3 8 6 25 17 30 23

В итоге ключевой элемент стоит на «своем месте», т.е. всплыл первый «пузырек». Слева (с 1-го по 5-ый элемент) и справа (с 7-го по 10-ый) от ключа элементы еще не упорядочены, применим к ним тот же метод, вызвав процедуру быстрой сортировки. Это уже будет второй уровень рекурсии.

Пример программы:

int n, a[n];//n - количество элементов

voidqs(int*s_arr, int first, int last)

{

int i = first, j = last, x =s_arr[(first + last)/2];

do{

while(s_arr[i]< x) i++;

while(s_arr[j]> x) j--;

if(i <= j){

if(i < j) swap(s_arr+ i, s_arr+ j);

i++;

j--;

}

}while(i <= j);

if(i < last)

qs(s_arr, i, last);

if(first < j)

qs(s_arr, first,j);

}