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
Болельщики вправе оспорить результат, но я им доволен.
Итоги
• Расположение данных в порядке возрастания или убывания называется сортировкой.
• Простейший алгоритм сортировки массива – «пузырьковая» сортировка. Она состоит в сравнении и перестановке соседних элементов массива, при этом организуются два вложенных цикла.
