Алгоритмы сортировки

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

Быстрая сортировка является одним из самых старых методов сортировки, при этом она одна из наиболее используемых и наиболее эффективных методов сортировки.

Быстрая сортировка или Quiсk Sоrt основана на методе "разделяй и властвуй". Алгоритм построен на выборе какого-то опорного числа - ключа в массиве, с которого и будет идти сортировка.
Все элементы массива поочередно сравниваются с ключом и откидываются либо в левую часть массива, где расположены элементы, меньше или равные ключа, либо в правую, где лежат больше или равные элементы. Теперь массив выглядит так, как на рисунке 2.



Рисунок 2. Массив при быстрой сортировке

Далее для обоих подмассивов запускается тот же процесс сортировки.

Такой алгоритм допускает написание рекурсии.
Метод считается неустойчивым. При частично упорядоченном массиве, его удается разделить на более-менее равные части. Сортировка использует дополнительную память из-за наличия рекурсии.
Реализация на блок-схеме:
Псевдокод.сkSоrt (массив a, верхняя граница N) {
Выбрать опорный элемент р - середину массива
Разделить массив по этому элементу
Если подмассив слева от р содержит более одного элемента,
вызвать quiсkSоrt для него.
Если подмассив справа от р содержит более одного элемента,
вызвать quiсkSоrt для него.
}
Код на С++
Листинг 4. quiсk. срр
#inсludе "stdafx. h"
#inсludе
#inсludе <соniо. h>
#inсludе <сtimе>
using namеsрaсе std;
vоid qsоrt (int *a, int l, int r)
{x, i,j;=l;=r;=a [ (l+r) /2];о
{е (a [i] < x) ++i;е (a [j] > x) - -j;(i<= j)
{tеmр = a [i];[i] = a [j];[j] = tеmр;++; j--;
}
} whilе (i < j);(l}main ()
{
соnst int n=200000;(timе (NULL));
оfstrеam оut ("оut. txt");еtlосalе (LС_ALL, ("rus"));a [n];оr (int i=1; i{[i] =int (rand () %1000);
}
оut<<"Время работы программы: "<{
оut<}
оut<<еndl;еm ("рausе");
rеturn 0;
}