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

Вначале ряд слитков он выложил, как попало. Затем стал по очереди сравнивать соседние куски. Если первый из них был тяжелее второго, аптекарь менял их местами. Так он сравнил первый и второй слитки, второй и третий, третий и четвертый и так далее до последнего слитка. В конце концов, самый тяжелый слиток оказался на последнем месте. Затем он повторил все это ещё раз, – и тогда второй по величине слиток оказался на предпоследнем месте. Проделав это N-1 раз, где N – количество слитков, лекарь выложил слитки в нужном порядке: первым лежал самый легкий, а последним – самый тяжелый.

Рис.89 – Пример справедливого дележа шести слитков между тремя пиратами

«А теперь бросайте жребий, – подытожил Нашатырь, скромно отходя в сторону, – пусть он определит порядок взятия долей». Пираты остались довольны.

Пузырьковая сортировка

Вернемся в наше время. О пиратской истории программист сказал бы так: разложив куски золота в нужном порядке, лекарь отсортировал массив слитков. Его метод известен как «пузырьковая сортировка» – Bubble Sort. Откуда взялось это название? Проследите за пузырьками в стакане газировки: по мере всплытия они объединяются с другими и становятся крупнее.

Воспользуемся методом лекаря-аптекаря для сортировки массива из 10 целых чисел – это будут наши золотые слитки. А для испытания алгоритма напишем программу «P_41_1», которая вначале заполнит массив случайным образом и распечатает его. Затем отсортирует этот массив и снова распечатает. Работу по сортировке выделим в отдельную процедуру по имени BubbleSort, – она ещё пригодится нам в последующих проектах.

Исследуйте процедуру сортировки по шагам. Здесь «крутятся» два цикла FOR-TO-DO, вложенные друг в друга. Внутренний цикл со счетчиком J сравнивает соседние числа и, при необходимости, меняет их местами. Переменная T нужна для перестановки соседних элементов. По завершении одного внутреннего цикла очередное крупное число оказывается на своем месте. Но, поскольку сортируются CSize чисел, то внутренний цикл надо повторить CSize-1 раз, – это делает внешний цикл со счетчиком I.

      { P_41_1 – Сортировка массива целых чисел }

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

      { объявление типа для массива }

type TGolds = array [1..CSize] of integer;

var Golds : TGolds; { массив кусков золота }

      { Процедура "пузырьковой" сортировки }

      { Внимание! Параметр-массив передается по ссылке! }

procedure BubbleSort (var arg: TGolds);

var i, j, t: Integer;

begin

for i:= 1 to CSize-1 do { внешний цикл }

      for j:= 1 to CSize-1 do { внутренний цикл }

      { если текущий элемент больше следующего …}

      if arg[j] > arg[j+1] then begin

      { то меняем местами соседние элементы }

      t:= arg[j];       { временно запоминаем }

      arg[j]:= arg[j+1];       { следующий -> в текущий }

      arg[j+1]:= t;       { текущий -> в следующий }

      end;

end;

var i:integer; { для индекса в главной программе }

begin {--- Главная программа ---}

      { заполняем массив случайным образом }

      Randomize;

      for i:=1 to CSize do Golds [i]:= 1+Random(1000);

      { распечатаем до сортировки }

      Writeln('До сортировки:');

      for i:=1 to CSize do Writeln(Golds [i]:3);

      { сортируем }

      BubbleSort(Golds);

      { распечатаем после сортировки }

      Writeln('После сортировки:');

      for i:=1 to CSize do Writeln(Golds [i]:3);

      Readln;

end.

Обратите внимание: сортируемый массив передан в процедуру по ссылке VAR. Передача в процедуры массивов, множеств, строк и других сложных типов данных по ссылкам CONST и VAR — обычная практика. Это повышает скорость работы программ и уменьшает объём памяти, занимаемый параматрами.