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

очень эффективный алгоритм, и известна как в среднем самая быстрая из универсальных алгоритмов сортировки. Быстрая сортировка сравнивает все элементы массива с одним, выбранным практически наугад, элементом (опорным элементом) и тем самым делит массив на две части - в одну попадают числа меньшие опорного, а в другую - большие опорного. Затем каждая из этих двух частей также подвергается аналогичной сортировке, и так до тех пор, пока очередная часть не окажется состоящей из единственного элемента.

Таким образом, быстрая сортировка - это рекурсивный алгоритм, то есть алгоритм вызывающий сам себя. Время быстрой сортировки пропорционально n*log(n). Однако, у алгоритма быстрой сортировки есть и недостатки. Массив случайных чисел сортируется очень быстро, однако только что отсортированный массив повторно процедура может обрабатывать крайне медленно, вплоть до полного исчерпания ёмкости стека, так как эффективность алгоритма крайне зависит от удачного выбора опорного элемента.

Здесь интересен метод разделения массива относительно опорного элемента. Для этого используются два разнонаправленных процесса. Первый начинает от начала массива и ищет элемент, больший опорного. Второй начинает с конца и ищет элемент, меньший опорного. Как только такие элементы найдены, производится их обмен местами, и далее поиск продолжается с того места, где процессы остановились.

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

Лучшим выбором для опорного элемента является средний элемент в массиве. Поэтому нужно выбирать опорным элемент, имеющий средний индекс. Это позволяет минимизировать вероятность самого неблагоприятного выбора - наименьшего элемента в массиве. Ещё лучше в качестве опорного выбирать элемент со средним значением из элементов с первым, последним и средним индексом.

Псевдокод алгоритма быстрой сортировки:

Процедура QuickSort(A: массив, min - начальный индекс, max - конечный индекс);
Начало
1. Выбрать supp - элемент со средним индексом (опорный):
2. Начать просмотр с начала массива и найти элемент, больший опорного A[i]> supp
3. Начать просмотр с конца массива и найти элемент, меньший опорного A[j]< supp
4. Если предыдущие процессы ещё не пересеклись (i не больше j), то
4.1. обменять найденные элементы местами
4.2. Перейти к п. 2. но не с начала массива, а с места предыдущей остановки
5. Проанализировать индексы последнего обмена.
5.1 Если i меньше max, то запустить QSuickSort(A, i, max)
5.2 Если j больше min, то запустить QSuickSort(A, min, j)
Конец процедуры

Вот реализация алгоритма быстрой сортировки:

type TArray: Array of Integer; //Параметры массива нужно определить до вызова процедуры

procedure qSort(var A: TArray; min, max: Integer);
var i, j, supp, tmp: Integer;
begin
supp: =A[max-Round((max-min)/2)];
i: =min; j: =max;
while i< j do
begin
while A[i]< basa do i: =i+1;
while A[j]> basa do j: =j-1;
if i< =j then
begin
tmp: =A[i]; A[i]: =A[j]; A[j]: =tmp;
i: =i+1; j: =j-1;
end;
end;
if min< j then qSort(A, min, j);
if i< max then qSort(A, i, max);
end;