Песни о Паскале - [84]

Исследуйте процедуру сортировки по шагам. Здесь «крутятся» два цикла 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, помните?). Что мы будем сортировать? Набранные очки? Да, но их надо как-то привязать к названиям команд.