Олег Деревенец - Песни о Паскале

Пусть друзья отдыхают, а мы поразмыслим, много ли толку в изобретении Лефта? Поскольку при каждом обмене арбузы перемещались на большое расстояние, то возможно, что таких обменов потребовалось меньше, чем при «пузырьке». Пока это лишь догадка, которую предстоит проверить. А пока соорудим и испытаем процедуру сортировки, придуманную Лефтом, назовём её FarmSort — «фермерская» сортировка.

Программа с процедурой перед вами. Введите её и проверьте, действительно ли процедура Лефта сортирует массив, не ошибся ли фермер?

{ P_43_1 проверка "фермерской" сортировки }

const

CSize=10; { размер массива }

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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