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

Глава 41 По порядку, становись!

Глава 41

По порядку, становись!

В 39-й главе, где состоялось наше знакомство с массивами, мы намерились отсортировать футбольные команды в порядке набранных ими очков. Следуя к этой цели, перенесемся ненадолго в прошлое, – лет на триста назад.

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

Однажды джентльменам удачи достался сундук с золотыми слитками. Пересчитав их, пираты выяснили, что каждому из них полагается ровно по два. Казалось бы, о чем тут думать? – садись и дели. Однако слитки существенно отличались формой и размерами. Пираты не могли распилить или переплавить их, сделав одинаковыми. Как быть? – с таким вопросом Райт обратился к экипажу.

После недолгих споров разбойники уже готовы были бросить жребий (на случайную дележку никто не обижался). Но тут голос подал бывший аптекарь, а ныне корабельный лекарь по кличке Нашатырь.

– Я предлагаю, – молвил Нашатырь, – разложить слитки в порядке их веса. Затем кто-то из нас возьмет самый легкий и самый тяжелый из них. Другой – самый легкий и самый тяжелый из оставшихся, и так далее.

Свою мысль он сопроводил рисунком с шестью слитками разного веса и размера (рис. 89).

– Отлично, – согласился Райт, – но как взвесить слитки? У нас нет ни гирь, ни весов.

– Зачем мне гири? Для сравнения слитков годится вот это, – и лекарь достал из своего сундука самодельные чашечные весы.

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

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

Вначале ряд слитков он выложил, как попало. Затем стал по очереди сравнивать соседние куски. Если первый из них был тяжелее второго, аптекарь менял их местами. Так он сравнил первый и второй слитки, второй и третий, третий и четвертый и так далее до последнего слитка. В конце концов, самый тяжелый слиток оказался на последнем месте. Затем он повторил все это ещё раз, – и тогда второй по величине слиток оказался на предпоследнем месте. Проделав это 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; { массив кусков золота }
      { Процедура "пузырьковой" сортировки }
      { Внимание! Параметр-массив передается по ссылке! }
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 — обычная практика. Это повышает скорость работы программ и уменьшает объём памяти, занимаемый параматрами.

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

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

Теперь каждый следующий внутренний цикл будет на единицу короче предыдущего (ведь счетчик внешнего цикла I растет). В следующей программе мы так и сделаем.

Рассмотрев хитрости пузырьковой сортировки, поможем теперь морским романтикам. Напишем программу для справедливой дележки золотых слитков. Основная работа уже проделана, – мы смогли отсортировать массив. Осталось лишь распечатать веса тех кусков, что достанутся каждому из пиратов. Известно, что первому пирату достанется первый и последний слитки, второму – второй и предпоследний и так далее. Иначе говоря, I–му пирату достанутся слитки с номерами I и CSize+1-I. Программа «P_41_2» «делит слитки», распечатывая после сортировки веса соответствующих пар.

{ P_41_2 – Пиратская делёжка по справедливости }
const CSize = 16; { размер массива слитков }
      { объявление типа для массива слитков }
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-i 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]:= 500 + Random(500);
      { сортируем }
      BubbleSort(Golds);
      Writeln('По справедливости:');
      for i:=1 to (CSize div 2) do begin
      { два куска по отдельности }
      Write(i:2, Golds[i]:5,' + ',Golds[CSize+1-i]:3,' = ');
      { сумма двух кусков }
      Writeln(Golds[i]+Golds[CSize+1-i] :4);
      end;
      Readln;
end.

Вот результат одной из таких делёжек:

По справедливости:
1 506 + 975 = 1481
2 556 + 967 = 1523
3 587 + 954 = 1541
4 629 + 916 = 1545
5 691 + 876 = 1567
6 694 + 872 = 1566
7 749 + 845 = 1594
8 751 + 800 = 1551

Здесь самый легкий и самый тяжелый слитки отличаются почти вдвое: 506 и 975 граммов. Но пары слитков, доставшихся пиратам, отличаются по весу незначительно.

Закаленные морскими приключениями, вернемся к сортировке футбольных клубов (задача поставлена в главе 39, помните?). Что мы будем сортировать? Набранные очки? Да, но их надо как-то привязать к названиям команд.

Поступим так. Объявим два массива: один (числовой) – для набранных очков, другой (строковый) – для названий клубов. При вводе данных элементы двух массивов будут соответствовать друг другу, поскольку имена команд и набранные ими очки вводятся одновременно. Затем, в ходе сортировки, переставляя элементы с очками, будем менять местами и соответствующие им элементы с названиями команд. Так имена команд последуют за очками, заработанными командами. Все это потребует небольших переделок в процедуре сортировки.

Впрочем, потребуется ещё одно мелкое изменение. Если при сортировке золотых слитков мы добивались возрастающего порядка, то теперь нужен противоположный, убывающий порядок сортировки. Как его добиться? Очень просто: изменим условие сравнения соседних элементов на противоположное. Вот собственно и все, осталось лишь показать программу «P_41_3».

{P_41_3 – Футбольный чемпионат }
const CSize = 16; { количество команд }
      { объявление типов для массивов }
type TAces = array [1..CSize] of integer; { тип для очков }
      TNames = array [1..CSize] of string; { тип для названий }
var Aces : TAces; { набранные очки }
      Names: TNames; { названия команд }
      { Процедура "пузырьковой" сортировки очков с именами команд }
procedure BubbleSort2(var arg1: TAces; var arg2: TNames);
var i, j, t: Integer;
      s: string;
begin
for i:= 1 to CSize-1 do { внешний цикл }
      for j:= 1 to CSize-i do { внутренний цикл }
      { если текущий элемент меньше следующего …}
      if arg1[j] < arg1[j+1] then begin
      { то меняем местами соседние элементы }
      t:= arg1[j];       { временно запоминаем }
      arg1[j]:= arg1[j+1]; { следующий -> в текущий }
      arg1[j+1]:= t;       { текущий -> в следующий }
      { меняем местами и названия команд }
      s:= arg2[j];       { временно запоминаем }
      arg2[j]:= arg2[j+1]; { следующий -> в текущий }
      arg2[j+1]:= s;       { текущий -> в следующий }
      end;
end;
var i: integer;
begin       { главная программа }
{ Вводим названия команд и набранные очки }
for i:=1 to CSize do begin
      Write('Название команды: '); Readln(Names[i]);
      Write('Набранные очки: '); Readln(Aces[i]);
end;
BubbleSort2(Aces, Names); { сортируем }
Writeln('Итоги чемпионата:');
Writeln('Место       Команда       Очки');
for i:=1 to CSize do
      Writeln(i:3,' ':3, Names[i], Aces[i]:20-Length(Names[i]));
Readln;
end.

Спецификатор ширины поля в операторе печати задан выражением.

      20 – Length(Names[i])

Здесь перед колонкой с очками будет тем больше пробелов, чем короче название команды, – так выравниваются колонки таблицы.

Для проверки программы я ввел наобум имена четырех команд нашего чемпионата и очки, якобы заработанные ими (количество команд CSize установил равным 4), и вот что у меня вышло.

Итоги чемпионата:
Место Команда       Очки
1 Локомотив       55
2 Крылья Советов 54
3 Спартак       47
4 Зенит       43

Болельщики вправе оспорить результат, но я им доволен.

• Расположение данных в порядке возрастания или убывания называется сортировкой.

• Простейший алгоритм сортировки массива – «пузырьковая» сортировка. Она состоит в сравнении и перестановке соседних элементов массива, при этом организуются два вложенных цикла.

А) Напишите программу для сортировки фамилий учеников в алфавитном порядке (фамилии берутся из файла). Программа должна сортировать их как по возрастанию, так и по убыванию фамилий, – на выбор пользователя.

Б) Придумайте самый несправедливый способ пиратской дележки по два слитка и напишите программу для неё.

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

Г) Напишите функцию, проверяющую, упорядочен ли числовой массив. Функция должна вернуть TRUE, если массив упорядочен по возрастанию. Массив внутрь функции передайте параметром по ссылке.

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