Песни о Паскале | страница 169

– Ну что ж, – сказал Райт, – ты придумал, тебе и делить.

И под пристальными взглядами всей команды лекарь принялся за дело.

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

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

Вернемся в наше время. О пиратской истории программист сказал бы так: разложив куски золота в нужном порядке, лекарь отсортировал массив слитков. Его метод известен как «пузырьковая сортировка» – 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; { массив кусков золота }

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