Песни о Паскале
Шрифт:
Глава 43
Сортировка по-взрослому
Наше
"Фермерская" сортировка
Отчего так медленно «всплывают пузырьки»? Не оттого ли, что мы сравниваем и обмениваем соседние элементы? Уяснить тонкости сортировки нам поможет правдивая история из жизни двух друзей.
Некий фермер — левша по имени Лефт — удостоился чести поставлять арбузы к столу Его Величества. Желая превзойти конкурентов и сохранить за собой королевский заказ, Лефт решил отбирать из урожая самые крупные ягоды (арбуз — это ягода). Выложив арбузы в длинный ряд, Лефт занялся их сортировкой. Работая в одиночку, он применил единственный доступный ему способ — «пузырёк». После трёх дней мучительных сравнений и перестановок Лефт понял, что без помощника ему не обойтись.
Сортировать урожай следующего года он позвал своего соседа и приятеля по имени Райт. Вдвоем они стали работать новым, придуманным Лефтом способом. Лефт стал у первого арбуза, а его приятель Райт побежал в конец ряда. Оттуда Райт стал продвигаться навстречу Лефту, сравнивая арбузы с тем, у которого прохлаждался Лефт (арбузы взвесили заранее, а вес нацарапали на кожуре). Когда Райт находил арбуз легче того, у которого стоял Лефт, их меняли местами: друзья просто швыряли арбузы друг другу.
Наконец Райт вплотную подошел к Лефту, и тогда на месте, где стоял Лефт, оказался самый легкий арбуз. Лефт шагнул ко второму арбузу, а Райт снова побежал в конец ряда, и всё повторилось. По окончании второго цикла на втором месте в ряду, где стоял Лефт, очутился второй по величине арбуз. Теперь первые два арбуза были отсортированы, и Лефт соизволил шагнуть к третьему. К сумеркам, совершив N-1 таких циклов, друзья закончили работу. Лефт, свежий как огурчик, ступил, наконец, к последнему арбузу, недоумевая, отчего его приятель Райт едва волочит ноги?
Рис. 94 – Сортировка массива с встречным движением индексов
Пусть друзья отдыхают, а мы поразмыслим, много ли толку в изобретении Лефта? Поскольку при каждом обмене арбузы перемещались на большое расстояние, то возможно, что таких обменов потребовалось меньше, чем при «пузырьке». Пока это лишь догадка, которую предстоит проверить. А пока соорудим и испытаем процедуру сортировки, придуманную Лефтом, назовём её 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.
Быстрая сортировка
«Здесь что-то не так, – стучало в голове Райта, пока он челноком мотался из конца в конец ряда, – почему я бегаю, а он стоит? Это несправедливо! К следующему урожаю я придумаю лучший способ сортировки!».
Через год Лефт опять позвал Райта на помощь.
Хорошо, – согласился Райт, – но теперь командовать буду я.
Пройдясь вдоль ряда, Райт прикинул на глазок вес среднего по величине арбуза. «Запомни этот вес, – сказал он Лефту, – и ступай к началу ряда», – а сам отправился в другой конец. «Теперь иди ко мне, пока не найдешь арбуз тяжелее указанного мною». Лефт так и сделал, – найдя первый такой арбуз, он остановился и крикнул об этом Райту. «Теперь моя очередь!» – отозвался Райт и стал двигаться навстречу Лефту, попутно отыскивая арбуз, легче среднего. Дойдя до такого арбуза, Райт остановился и скомандовал: «Меняем арбузы местами!», – и друзья швырнули арбузы друг другу.
– Снова твоя очередь! – крикнул Райт, – продолжай двигаться ко мне! – а сам присел отдохнуть.
Так поочередно друзья шли навстречу друг другу, время от времени обмениваясь арбузами. Где то в середине ряда они встретились.
– Ну и чем обернулась твоя идея со средним арбузом? – ядовито осведомился Лефт, – мы уже встретились, не отсортировав ни единого!
– Да, – согласился Райт, – зато любой арбуз на твоей левой половине ряда легче любого на моей правой половине.
– Откуда ты знаешь?
– Оттуда! Ведь все твои арбузы легче среднего, а все мои – тяжелее!
– Да, пожалуй, так, но что нам это даёт? – не унимался Лефт.
– А то, что теперь эти две половинки ряда можно сортировать отдельно. Смекнул? Нам меньше бегать придется, ведь расстояния вдвое короче!
– И как же мы будем сортировать эти половинки?
– Тем же порядком, но по очереди, – сначала твою половину, потом мою.
И Райт стал прикидывать средний вес арбузов в левой половине ряда. Этот средний вес был, разумеется, меньше того, что в первом случае. Переведя дух, друзья повторили те же действия с левой половиной ряда. В серединке этой половинки они встретились вновь.