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

Задача. Задана последовательность из 1000 целых чисел. Переставить элементы последовательности таким образом, чтобы они располагались в порядке неубывания.

Решение. Задача допускает следующее очевидное решение с использованием целочисленного массива $M$ из 1000 элементов:

1) ввод исходной последовательности в массив $M$;

2) так называемая сортировка массива $M$ или, что то же самое, перестановка его элементов в порядке, при котором

$$(\forallK:1\leq K < 1000: M[K] \leq M[K+1]);$$

3) печать элементов массива $M$ в порядке возрастания их индексов.

Первый и третий шаги очевидны, а для сортировки массива $M$ можно использовать следующий довольно простой и весьма эффективный метод.

Рассмотрим элемент, находящийся посередине массива $M$ (назовем его $X$). Затем начнем осуществлять два встречных просмотра массива: двигаемся слева направо, пока не найдем элемент $M[I]>X,$ и справа налево, пока не найдем элемент $M[J]<X.$ Когда указанные элементы будут найдены, поменяем их местами и продолжим процесс "встречных просмотров с обменами", пока два идущих навстречу друг другу просмотра не встретятся. В результате массив разделится на две части: левую, состоящую из элементов меньших или равных $X$, и правую, в которую попадут элементы, большие или равные $X.$ После такого разделения массива $M,$ чтобы завершить его сортировку, достаточно осуществить то же самое с обеими полученными частями, затем с частями этих частей и т.д., пока каждая часть не будет содержать ровно один элемент.

Реализация указанного метода приводит к следующему (рекурсивному!) решению задачи сортировки:

module БыстраяСортировка;
    const N = 1000;
    type НОМЕР = integer; МАССИВ=array N+1 of integer;
    var M: МАССИВ; I: НОМЕР;
    procedure QuickSort(L, R: НОМЕР);
        var I, J, X, Y: НОМЕР;
    begin I := L; J := R; X := M[(L+R) div 2];
          repeat
                while M[I] < X do I := I + 1end;
                while X < M[J] do J := J - 1end;
                if I <= J then
                       Y := M[I]; M[I] := M[J]; M[J] := Y;
                        I := I + 1; J := J - 1;
                end
                (* $\{(\forall K: L\leq K\leq I: M[K]\leq X),$$(\forall K: J\leq K\leq R: X \leq M[K])\}$*)
          until I > J;
          if L < J then QuickSort(L, J) end;
          if I < R then QuickSort(I, R) end;
    end QuickSort;
begin
    for I:=1 to N do read(M[I]) end;
    QuikSort(1,N); (* $\{(\forall K: L\leq K< R: M[K]\leqM[K+1])\}$ *)
    for I:=1 to N do write(M[I]) end;
end БыстраяСортировка.
 

Указанный метод из-за своих хороших временных характеристик получил название "быстрой сортировки".