Книга: Песни о Паскале

Глава 43 Сортировка по-взрослому

Глава 43

Сортировка по-взрослому

Наше новейшее открытие – быстрый, как ракета, двоичный поиск. Но работает он лишь в сортированном массиве. Так в чем вопрос? Разве сортировка «пузырьком» нам не покорилась? Увы! «Пузырек» насколько же нетороплив, насколько и прост. Много ли проку от быстрого поиска, если выигрыш времени съест сортировка? Так ускорим её!

Отчего так медленно «всплывают пузырьки»? Не оттого ли, что мы сравниваем и обмениваем соседние элементы? Уяснить тонкости сортировки нам поможет правдивая история из жизни двух друзей.

Некий фермер — левша по имени Лефт — удостоился чести поставлять арбузы к столу Его Величества. Желая превзойти конкурентов и сохранить за собой королевский заказ, Лефт решил отбирать из урожая самые крупные ягоды (арбуз — это ягода). Выложив арбузы в длинный ряд, Лефт занялся их сортировкой. Работая в одиночку, он применил единственный доступный ему способ — «пузырёк». После трёх дней мучительных сравнений и перестановок Лефт понял, что без помощника ему не обойтись.

Сортировать урожай следующего года он позвал своего соседа и приятеля по имени Райт. Вдвоем они стали работать новым, придуманным Лефтом способом. Лефт стал у первого арбуза, а его приятель Райт побежал в конец ряда. Оттуда Райт стал продвигаться навстречу Лефту, сравнивая арбузы с тем, у которого прохлаждался Лефт (арбузы взвесили заранее, а вес нацарапали на кожуре). Когда Райт находил арбуз легче того, у которого стоял Лефт, их меняли местами: друзья просто швыряли арбузы друг другу.

Наконец Райт вплотную подошел к Лефту, и тогда на месте, где стоял Лефт, оказался самый легкий арбуз. Лефт шагнул ко второму арбузу, а Райт снова побежал в конец ряда, и всё повторилось. По окончании второго цикла на втором месте в ряду, где стоял Лефт, очутился второй по величине арбуз. Теперь первые два арбуза были отсортированы, и Лефт соизволил шагнуть к третьему. К сумеркам, совершив N-1 таких циклов, друзья закончили работу. Лефт, свежий как огурчик, ступил, наконец, к последнему арбузу, недоумевая, отчего его приятель Райт едва волочит ноги?

Пусть друзья отдыхают, а мы поразмыслим, много ли толку в изобретении Лефта? Поскольку при каждом обмене арбузы перемещались на большое расстояние, то возможно, что таких обменов потребовалось меньше, чем при «пузырьке». Пока это лишь догадка, которую предстоит проверить. А пока соорудим и испытаем процедуру сортировки, придуманную Лефтом, назовём её 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вы принимаете эту формулу? Тогда перейдем к процедуре быстрой сортировки по имени 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 – строка сообщения }
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('До сортировки:');
      QuickSort(Arr, 1, CSize);
      ShowArray('После сортировки:');
end.

Взгляните на параметры процедуры QuickSort. Вместе со ссылкой на массив, в процедуру передаются левая (aL) и правая (aR) границы сортируемой части массива (индексы). В процедуре вычисляется вес среднего арбуза по выбранной нами формуле и организуется поочередное встречное движение левого и правого индексов.

Самое интересное происходит после «встречи» индексов, когда массив разбит на две части. Удивительно, что теперь снова дважды вызывается та же самая процедура QuickSort: сначала для левой части массива, а затем – для правой (эти операторы выделены курсивом). Вспомните, – точно так же поступали и фермеры при сортировке арбузов.

«Так там фермеры, а здесь Паскаль! Позволено ль процедуре вызывать саму себя?» – слышу недоверчивый вопрос. Мы свыклись с тем, что из одной процедуры вызывают другую, из второй, – третью и так далее. Но чтобы саму себя? Это ж змея, глотающая свой хвост! Не оттого ли запутался фермер Лефт?

Такой самовызов процедур называют рекурсией. «У попа была собака…» – помните? Это рекурсия, познакомимся с нею ближе (с рекурсией, а не собакой).

Легко заметить, что повторные вызовы процедуры QuickSort выполняются с другими значениями левой и правой границ. Чем глубже вызов, тем уже эти границы. С некоторого момента условия (R > aL) и (L < aR) перестают выполняться, и происходит выход из процедуры, – здесь фермеры возвращаются к несортированным частям массива. Таким образом, при выходе мы снова попадаем в эту же процедуру, но в другое место – следующее за вызовом. Окончательный выход из процедуры в главную программу случится только по завершении сортировки всего массива!

Напрашивается вопрос: какова судьба локальных переменных и параметров при повторных входах в процедуру? Ведь они изменятся, а это должно нарушить работу процедуры. Параметры и локальные переменные действительно изменяются, но это не путает алгоритм. Почему?

Разгадка в том, что при каждом входе в процедуру для её параметров и локальных переменных выделяется новый участок памяти. Теперь это будут уже другие параметры и локальные переменные, но с прежними названиями. Однако предыдущие их значения не теряются, а сохраняются в памяти, называемой стеком (Stack).

Что такое стек и как он работает? Случалось ли вам паковать рюкзак или глубокую сумку? Тогда вы знакомы со стеком. Все, что уложено в рюкзак, будет извлекаться из него в обратном порядке. Так же устроен и стек: при каждом вызове процедуры память для параметров и локальных переменных выделяется на его вершине. Эти новые значения временно закрывают предыдущие значения параметров, и так происходит при каждом входе в процедуру.

При выходе из неё последние значения параметров и локальных переменных удаляются с вершины стека, и тогда вновь открываются ранее скрытые. Так процедура «вспоминает» о неоконченной работе, и продолжает действия с параметрами, сохраненными в стеке ранее. В некоторый момент стек пустеет (когда все вещи из рюкзака вынуты), и тогда происходит окончательный выход из процедуры в главную программу.

Механизм стековой памяти заложен в конструкцию процессора, и он не требует участия программиста. Стек используется для любых процедур и функций, а не только рекурсивных.

Но стоп! О стеке поговорим позже, а сейчас займемся делом. Введите программу «P_43_2» и убедитесь в её правильной работе.

Теперь в нашем распоряжении есть три процедуры сортировки, не устроить ли состязание между ними? На старт вызываются:

• BubbleSort – «пузырьковая» сортировка,

• FarmSort – «фермерская» сортировка,

• QuickSort – быстрая сортировка.

Время «спортсменов» мы будем засекать не по часам. И вы знаете, почему: мы сравниваем алгоритмы, а не компьютеры. В 42-й главе, где сравнивались алгоритмы поиска, мы оценивали время по количеству выполненных шагов. Поступим и здесь похожим образом. Вспомним, в чем состоит сортировка? – в сравнениях и перестановках. И много-много раз… Значит, трудоемкость сортировки можно оценить количеством этих двух операций – сравнений и перестановок, надо их только посчитать.

Что ж, дело нехитрое, сейчас посчитаем, – перед вами программа для наших опытов («P_43_3»). Количество сравнений и перестановок будем накапливать в переменных C1 и C2. Обратите внимание на их тип – EXTENDED, – это переменные действительного типа. Почему не длинное целое? При сортировке больших массивов может потребоваться столь много операций, что не хватит целочисленной переменной, – она переполнится, «лопнет», и результат исказится. Потому выбран тип EXTENDED.

Далее в программе следуют знакомые вам процедуры сортировки, – это наши «спортсмены». В их тела «вживлены» дополнительные операторы для подсчета сравнений (C1) и перестановок (C2), – они выделены курсивом. Наконец, главная программа, – она вызывает по очереди каждую из процедур и печатает количество сравнений и перестановок. Здесь равные условия для соревнующихся создаются загодя сформированным случайным массивом Arr0, который копируется в массив Arr перед каждой сортировкой.

Вам осталось лишь задать размер массива константой CSize, скомпилировать и запустить программу.

{ P_43_3 – Сравнение алгоритмов сортировки }
const CSize=100; { размер массивов }
type TNumbers = array [1..CSize] of Integer;
var Arr0 : TNumbers; { несортированный массив-заготовка }
      Arr : TNumbers; { сортируемый массив }
      C1, C2 : extended; { счетчики сравнений и перестановок }
{ BubbleSort "пузырьковая" сортировка }
procedure BubbleSort(var arg: TNumbers);
var i, j, t: Integer;
begin
      for i:= 1 to CSize-1 do
      for j:= 1 to CSize-i do begin
      C1:=C1+1; { подсчет сравнений }
      if arg[j] > arg[j+1] then begin
      C2:=C2+1; { подсчет перестановок }
      t:= arg[j]; arg[j]:= arg[j+1]; arg[j+1]:= t;
      end;
      end;
end;
{ FarmSort – «Фермерская» сортировка }
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
      C1:=C1+1; { подсчет сравнений }
      if arg[L] > arg[R] then begin
      C2:=C2+1; { подсчет перестановок }
      T:= arg[L]; arg[L]:= arg[R]; arg[R]:= T;
      end;
      end;
end;
      { QuickSort – Быстрая сортировка }
procedure QuickSort(var arg: TNumbers; aL, aR: Integer);
var
L, R, Mid, T: Integer;
begin
L:= aL; R:= aR;
Mid:= (arg[L] + arg[(L + R) div 2] + arg[R]) div 3;
repeat
      while arg[L] < Mid do begin L:=L+1; C1:=C1+1 end;
      while arg[R] > Mid do begin R:=R-1; C1:=C1+1 end;
      if L <= R then begin
      if arg[L]>arg[R] then begin
      C2:=C2+1; { подсчет перестановок }
      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;
const CFName = 'P_43_3.out';
var i: integer;
F: text;
begin
Assign(F,CFName); Rewrite(F);
for i:=1 to CSize do Arr0[i]:=1+Random(10000);
Writeln(F, 'Размер массива = ', CSize);
Writeln(F, 'Алгоритм       Количество Количество');
Writeln(F, 'сортировки сравнений перестановок');
C1:=0; C2:=0;       { очистить счетчики }
Arr:= Arr0;       { заполнить сортируемый массив }
BubbleSort(Arr);
Writeln(F, 'Пузырьковая:', C1:12:0, C2:12:0);
C1:=0; C2:=0;       { очистить счетчики }
Arr:= Arr0;       { заполнить сортируемый массив }
FarmSort(Arr);
Writeln(F, 'Фермерская :', C1:12:0, C2:12:0);
C1:=0; C2:=0;       { очистить счетчики }
Arr:= Arr0;       { заполнить сортируемый массив }
QuickSort(Arr, 1, CSize);
Writeln(F, 'Быстрая :', C1:12:0, C2:12:0);
Writeln('OK !'); Readln;
Close(F);
end.

Вот что получилось для массива из 1000 элементов.

Размер массива = 1000
Алгоритм       Количество Количество
сортировки сравнений перестановок
Пузырьковая: 499500       248061
Фермерская : 499500       80887
Быстрая :       5871       2417

Я провел три опыта с массивами из 100, 1000 и 10000 элементов, а результаты занес в две таблички. Что сказать по этому поводу?

Табл. 9 – Количество сравнений в разных методах сортировки

Из табл. 9 следует, что по количеству сравнений «Фермерская» сортировка не лучше «пузырька». Зато быстрая сортировка оправдывает свое название, – выигрыш составляет от 10 до 600 раз! И чем больше массив, тем заметней этот разрыв.

Табл. 10 – Количество перестановок в разных методах сортировки

А что с количеством перестановок (табл. 2)? Здесь «фермерская» сортировка всё же в 3—4 раза обгоняет «пузырёк». Так что фермеру Лефту в сметливости не откажешь. И всё же этому «спортсмену» далеко до изобретения Райта! В сравнении с «пузырьком» выигрыш стократный, и стремительно растёт с ростом размера массива. Слава, слава фермеру Райту! Кстати, историки выяснили его настоящее имя: это англичанин Чарльз Хоар.

Итак, с чемпионом все ясно (рис. 96), но в чем секрет его успеха? Сравним чемпиона с отставшими. Чем больше массив, тем дольше он сортируется, – это справедливо для любого алгоритма. Долгие методы обрабатывают весь массив N раз, где N – размер массива. Поэтому их трудоемкость пропорциональна произведению N•N. По этой формуле вычисляют площадь квадрата, и такую зависимость называют квадратичной.

Иное дело – чемпион. Дробя массив на мелкие участки, быстрый алгоритм уменьшает число прохождений всего массива до величины Log₂N. Поэтому его трудоемкость растёт пропорционально произведению N•Log₂N. Опять логарифм? Да, мы помним его по двоичному поиску. Поскольку логарифм числа растёт очень медленно, это объясняет чемпионство QuickSort (рис. 97).

• Двоичный поиск – это самый быстрый способ поиска, но он требует предварительной сортировки массива.

• Простые методы сортировки – BubbleSort и FarmSort – работают очень медленно, съедая всю экономию от двоичного поиска.

• QuickSort – это быстрый способ сортировки, который в сочетании с резвым двоичным поиском ускорит работу ваших программ.

А) Исследуйте процедуру быстрой сортировки в пошаговом режиме (задайте небольшой размер сортируемого массива). Обратите внимание на изменение границ сортируемой части.

Б) Определите количество повторных входов в процедуру QuickSort и выходов из нее. Объявите глобальную переменную, назовем её Level – «уровень». В главной программе, перед вызовом процедуры QuickSort, эту переменную надо обнулить, а внутри процедуры добавить следующие операторы.

В начале процедуры QuickSort:

begin
      Inc(Level); Writeln('Уровень на входе = ', Level);

В конце процедуры QuickSort:

      Dec(Level); Writeln('Уровень на выходе = ', Level);
end;

В) Если каждый вызов QuickSort делит массив примерно пополам, то наибольшее значение переменной Level должно составить приблизительно Log₂N (у нас размер массива задан константой CSize). Проверьте эту догадку компиляцией и запуском программы для нескольких значений CSize.

Г) В одном ряду вперемежку лежат дыни и арбузы. Могут ли фермеры отсортировать их за один проход ряда так, чтобы в начале оказались все дыни, а в конце ряда – все арбузы? Напишите такую программу, обозначив арбузы единицами, а дыни – нулями.

Оглавление книги