Песни о Паскале

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

К счастью, все не так уж плохо. Опыт показал, что делить массив строго пополам совсем не обязательно. Например, при делении ряда в пропорции 1/3 и 2/3 сортировка почти не ухудшится. Значит, можно оценивать вес среднего арбуза «на глазок» (как это делал Райт). Будем вычислять его как среднее арифметическое для трех арбузов: двух крайних и того, что лежит в середине сортируемой части массива.

Тогда формула для определения веса среднего арбуза будет такой:

      Средний вес := (Вес[L] + Вес[(L + R)/2] + Вес [R]) / 3;

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

Рис. 95 – Изменения массива при «быстрой» сортировке

Вы принимаете эту формулу? Тогда перейдем к процедуре быстрой сортировки по имени QuickSort (Quickly – «быстро», Sort – «сортировка»). Вот она вместе с проверяющей её программой.

{ P_43_2 QuickSort – Быстрая сортировка }
const CSize=10; { размер массива }
type TNumbers = array [1..CSize] of Integer;
var Arr : TNumbers;
      { Процедура быстрой сортировки }
procedure QuickSort(var arg: TNumbers; aL, aR: Integer);
var
      L, R : integer; { левый и правый индексы }
      M, T : Integer; { среднее значение и временное хранилище }
begin
      { Начальные значения левого и правого индексов }
      L:= aL; R:= aR;
      { Вычисляем среднее по трём (порог для сравнения ) }
      M:= (arg[L] + arg[(L + R) div 2] + arg[R]) div 3;
      repeat       { Цикл встречного движения }
      { Пока левый элемент меньше среднего,
      двигаем левый индекс вправо }
      while arg[L] < M do L:=L+1;
      { Пока правый элемент больше среднего,
      двигаем правый индекс влево }
      while arg[R] > M do R:=R–1;
      { После остановки сравниваем индексы }
      if L <= R then begin
      { Здесь индексы ещё не "встретились", поэтому,
      если левый элемент оказался больше правого,
      меняем их местами }
      if arg[L]>arg[R] then begin
      t:= arg[L]; arg[L]:= arg[R]; arg[R]:= t;
      end;