Песни о Паскале - [90]

type
      TNumbers = array [1..CSize] of Integer; { тип для массива }
var
      Arr : TNumbers;       { сортируемый массив }

      { Процедура "фермерской" сортировки }
procedure FarmSort(var arg: TNumbers);
var L, R, T: Integer;
begin
for L := 1 to CSize-1 do
      { Сдвигаем правый индекс влево }
      for R := CSize downto L+1 do begin
      { Если левый элемент оказался больше правого,
      то меняем элементы местами }
      if arg[L] > arg[R] then begin
      { Перестановка элементов массива }
      T:= arg[L]; arg[L]:= arg[R]; arg[R]:= T;
      end;
      end;
end;

      { Процедура распечатки массива, arg – строка сообщения }
procedure ShowArray(const arg: string);
var i: integer;
begin
      Writeln(arg);
      for i:=1 to CSize do Writeln(Arr[i]);
      Readln;
end;
var i: integer;
begin
      { Заполняем массив случайными числами }
      for i:=1 to CSize do Arr[i]:=1+Random(1000);
      ShowArray('До сортировки:');
      FarmSort(Arr);
      ShowArray('После сортировки:');
end.

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

«Здесь что-то не так, – стучало в голове Райта, пока он челноком мотался из конца в конец ряда, – почему я бегаю, а он стоит? Это несправедливо! К следующему урожаю я придумаю лучший способ сортировки!».

Через год Лефт опять позвал Райта на помощь.

Хорошо, – согласился Райт, – но теперь командовать буду я.

Пройдясь вдоль ряда, Райт прикинул на глазок вес среднего по величине арбуза. «Запомни этот вес, – сказал он Лефту, – и ступай к началу ряда», – а сам отправился в другой конец. «Теперь иди ко мне, пока не найдешь арбуз тяжелее указанного мною». Лефт так и сделал, – найдя первый такой арбуз, он остановился и крикнул об этом Райту. «Теперь моя очередь!» – отозвался Райт и стал двигаться навстречу Лефту, попутно отыскивая арбуз, легче среднего. Дойдя до такого арбуза, Райт остановился и скомандовал: «Меняем арбузы местами!», – и друзья швырнули арбузы друг другу.

– Снова твоя очередь! – крикнул Райт, – продолжай двигаться ко мне! – а сам присел отдохнуть.

Так поочередно друзья шли навстречу друг другу, время от времени обмениваясь арбузами. Где то в середине ряда они встретились.

– Ну и чем обернулась твоя идея со средним арбузом? – ядовито осведомился Лефт, – мы уже встретились, не отсортировав ни единого!

– Да, – согласился Райт, – зато любой арбуз на твоей левой половине ряда легче любого на моей правой половине.

– Откуда ты знаешь?

– Оттуда! Ведь все твои арбузы легче среднего, а все мои – тяжелее!

– Да, пожалуй, так, но что нам это даёт? – не унимался Лефт.

– А то, что теперь эти две половинки ряда можно сортировать отдельно. Смекнул? Нам меньше бегать придется, ведь расстояния вдвое короче!

– И как же мы будем сортировать эти половинки?

– Тем же порядком, но по очереди, – сначала твою половину, потом мою.

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

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

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

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

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

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

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

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

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

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

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

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

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

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