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

тяжелый слиток оказался на последнем месте. Затем он повторил все это ещё раз, – и тогда второй по величине слиток оказался на предпоследнем месте. Проделав это 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);
      { распечатаем до сортировки }