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

Этот один из самых быстрых алгоритмов сортировки, получил свое название от стандартной библиотеки языка Си – quicksort. Он был разработан английским информатиком Чарльзом Хаором в 1960 году.

Алгоритм разработан на базе алгоритма пузырьковой сортировки. Улучшение старого алгоритмов заключается в том, что перестановки производятся для элементов на наиболее возможном расстоянии и сам список последовательно разделяется на отдельные группы.

Механизм работы алгоритма заключается в следующем:

• выбор опорного элемента – это может быть произвольный элемент массива, от которого зависит дальнейшая эффективность алгоритма;
• сравнение элементов массива с опорным элементом, размещая в двух группах, выбирая значения больше опорного элемента или меньше;
• повторение предыдущих операций для каждой группы элементов;
• получив, рекурсивно разбитый алгоритм на небольшие уже неделимые части массива, производится сборка в единый отсортированный массив.

const
    N = 10; // размер массива

type
    TMas = array[1..N] of Integer; // создание типа данных массив *

var
    mas : TMas; // создание массива

    procedure sort(var mas : TMas; low, high: integer);
    var
        i, j, k, h: integer;
    begin
        i := low;
        j := high;
        k := mas[(i + j) div 2]; // средний элемент в массиве берется в качестве опорного

        repeat
     // если в этих условиях заменить знаки сравнения на обратные, будет выполняться сортировка по убыванию
         while mas[i] < k do i := i + 1;
         while mas[j] > k do j := j - 1;

         if i <= j then begin // замена элементов местами
              h := mas[i];
              mas[i] := mas[j];
              mas[j] := h;
              i := i + 1
              j := j + 1
           end;
     until i > j;

     // рекурсивный вызов процедуры сортировки для частей массива
     if low < j then
        sort(mas, low, j);
     if i < high then
        sort(mas, i, high);
   end;

begin
   sort(mas, Low(mas), High(mas)); // основной вызов процедуры сортировки
end;

* Для задачи массива здесь используется задание типа массива с последующим созданием переменной этого типа. Сделано для того, чтобы можно было задать массив одного типа, как для глобального массива, так и для локального массива в функции.