6. Внутренняя сортировка данных «быстрым» методом. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
Быстрая сортировка часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении nэлементов), хотя и имеющий ряд недостатков.
Достоинства:
быстрота, простота реализации, хорошо
сочетается с механизмами кэширования
и виртуальной памяти. Требует
лишь 
дополнительной
памяти для своей работы. (Не улучшенный
рекурсивный алгоритм в худшем
случае 
памяти).
Существует эффективная модификация
(алгоритм Седжвика)
для сортировки строк — сначала
сравнение с опорным элементом только
по нулевому символу строки, далее
применение аналогичной сортировки для
«большего» и «меньшего» массивов тоже
по нулевому символу, и для «равного»
массива по уже первому символу.
Недостатки:
Сильно деградирует по скорости (до
)
при неудачных выборах опорных элементов,
что может случиться при неудачных
входных данных. Этого можно избежать,
используя такие модификации алгоритма,
как Introsort,
или вероятностно, выбирая опорный
элемент случайно, а не фиксированным
образом.Наивная реализация алгоритма может привести к ошибке переполнения стека, так как ей может потребоваться сделать вложенных рекурсивных вызовов. В улучшенных реализациях, в которых рекурсивный вызов происходит только для сортировки меньшей из двух частей массива, глубина рекурсии гарантированно не превысит .
Неустойчив — если требуется устойчивость, приходится расширять ключ.
Эффективность:
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод.
Оценим эффективность метода быстрой сортировки. На каждом шаге делим массив на две части, для каждой из этих частей – N/2 сравнений (всего – 2*N/2=N), затем на 2-ом шаге снова делим, получаем N/4 сравнений (4*N/4=N) и т.д. Так как глубина рекурсии (количество разбиений) равна Log2N, а количество сравнений на каждом уровне – 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=5 j=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
14
6 7 3 8 6 25 17 30 23
В итоге ключевой элемент стоит на «своем месте», т.е. всплыл первый «пузырек». Слева (с 1-го по 5-ый элемент) и справа (с 7-го по 10-ый) от ключа элементы еще не упорядочены, применим к ним тот же метод, вызвав процедуру быстрой сортировки. Это уже будет второй уровень рекурсии.
Пример программы:
int n, a[n]; //n - количество элементов
void qs(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);
}