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

– Видишь, как быстро мы сошлись, – отметил Райт, – а все потому, что ряд стал вдвое короче. Теперь все арбузы в левой четвертинке легче тех, что в правой четвертинке. Продолжим действовать так же, и отсортируем четвертинки по отдельности.

И фермеры продолжили дележку ряда: первую четвертинку разбили на две осьмушки, первую осьмушку – на две шестнадцатых и так далее, пока кусочек ряда не съежился до одного-двух арбузов. Этот кусочек они отсортировали моментально и пружина стала раскручиваться в обратную сторону. В конце концов, они вернулись к оставленным ранее частям ряда и отсортировали вторую осьмушку, вторую четвертинку и вторую половинку.

– Готово! – радостно выдохнул Райт. – Гляди-ка, ещё утренняя роса не просохла!

– Нич-ч-чо не понимаю, – сдался Лефт, – но ты, похоже, гений!

И приятели отправились завтракать.

Процедура быстрой сортировки

Друзья заслужили отдых, и теперь наш черед. Возьмем алгоритм Райта и проверим, так ли он хорош?

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

К счастью, все не так уж плохо. Опыт показал, что делить массив строго пополам совсем не обязательно. Например, при делении ряда в пропорции 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;

      { Индексы «делают шаг» навстречу друг другу }

      L:=L+1; R:=R-1;

      end;

      until L > R; { пока индексы не "встретятся" }

      { если левая часть не отсортирована, то сортируем её }

      if R > aL then QuickSort(arg, aL, R);

      { если правая часть не отсортирована, то её тоже сортируем }

      if L < aR then QuickSort(arg, L, aR);

      { выход после сортировки обеих частей }

end;

      { Процедура распечатки массива, arg – строка сообщения }