Алгоритм сортировки методом пузырька

 

Рассмотрим, как программируется сортировка массива. Для решения этой задачи существует целый класс алгоритмов. Мы рассмотрим здесь только один из них, известный под названием «метод пузырька». Откуда такое название, станет ясно немного позже.

Проиллюстрируем идею метода пузырька на маленьком массиве из пяти чисел. Пусть это будет массив В [1:5], исходные значения в котором распределены случайным образом (рис. 2.16). Требуется отсортировать числа по убыванию.

 

 

Первый этап (первый проход). Последовательно сравниваются пары соседних чисел и упорядочиваются по убыванию. Сначала сравниваются В[1] и В[2]. Поскольку на втором месте должно стоять меньшее число, то числа меняются местами. В[1] становится равным 3, В[2] — равным 1. Затем упорядочиваются В[2] и В[3]. Их значения тоже переставляются: В[2]=2, В[3]=1. Затем упорядочиваются В[3] и В[4]. И наконец, В[4] и В[5]. В результате первого прохода минимальное число попадает на свое место: В[5]=1.

 

Алгоритм первого прохода можно описать так:

Для I от 1 до 4 повторять

нц

если В[I]<В[I+1] то

X:=B[I]; В[I]:=В[I+1]; В[I+1]:=X

кв

кц

 

Обмен значениями В[I] и В[I+1] происходит через третью переменную X.

Вот теперь можно понять смысл образа пузырька! В результате прохода минимальное значение «всплывает» в конец массива, как воздушный пузырек в воде всплывает на поверхность, подталкиваемый архимедовой силой.

Далее нужно повторять такие проходы еще три раза. После второго прохода на своем месте окажется В[4], после третьего прохода — В[3]. После четвертого прохода упорядочатся В[2] и В[1]. Нетрудно понять, что при втором проходе не надо трогать В[5], т. е. цикл должен повторяться для / от 1 до 3. При третьем проходе — от 1 до 2. И наконец, на четвертом проходе — от 1 до 1, т. е. всего 1 раз.

Следовательно, циклы, реализующие проходы, сами должны циклически повторяться. Причем при каждом следующем повторении длина цикла должна уменьшаться на единицу. Отсюда вывод: структура алгоритма должна представлять собой два вложенных цикла.

 

Вот полный алгоритм сортировки массива В[1:16]:

алг Сортировка методом пузырька

цел таб В[1:16]

цел I, К, X

Нач

{Цикл ввода}

Для I от 1 до 16 повторять

нц

Вывод "В[", I, "]="

Ввод В[I]

кц

{Циклы сортировки}

Для К от 1 до 15 повторять

нц

Для I от 1 до 16-К повторять

нц

если В[I]<В[I +1]

то X:=B[I]; В[I]:=В[I +1]; В[I +1]:=Х

кц

кц

{Вывод отсортированного массива}

Для I от 1 до 16 повторять

нц

Вывод "В[”, I, В[I]

кц

Кон

 

Здесь переменная К играет роль номера прохода. Для массива длиной 16 такие проходы требуется повторить 15 раз. Длина каждого. К -го прохода равна 16- К.

 

Программа на Паскале сортировки методом пузырька

 

Теперь запишем программу на Паскале. Но мы ее немного усложним по сравнению с построенным алгоритмом. По условию исходной задачи нам нужно получить список команд в порядке занятых ими мест и число очков, полученных каждой командой. Следовательно, сортировать нужно не только массив В, но и массив Team. Делается это очень просто: в массиве Team параллельно с массивом В производятся те же самые перестановки. В конце работы программы на экран выводятся одновременно элементы обоих отсортированных массивов.

 

Program Premier__liga_2;

var В: array[1..16] of integer;

Team: array[1..16] of string;

I, К, X: integer;

St: string;

Begin

{Ввод названий команд и набранных ими очков}

writeln('Введите названия команд и полученные ими очки');

for I:=l to 16 do

Begin

write (I,' Название: '); Readln(Team[I]);

write('Очки: '); Readln(В[I])

end;

{Сортировка}

for K:=l to 15 do

for I:=l to 16-K do

if (В[I] < В[I +1]) then

Begin

X:=B[I]; В[I]:=B[I+1]; B[I+1]:=X;

St:=Team[I]; Team[I]:=Team[I+1];

Team[I+1]:=St

end;

{Вывод отсортированной таблицы}

for I:=l to 16 do

Begin

{Присоединение пробелов к названиям команд}

for K:=l to 18-length(Team[I]) do

Team[I]:=Team[I]+' ';

{Вывод: место, команда, очки}

writeln (1:2, ' ',Team[I]:18,В[I]:2)

End

End.

 

Поясним новые средства Паскаля, которые применены в этой программе. Обмен значениями между элементами строкового массива Team должен происходить через переменную строкового типа. Для этого в программе используется переменная St.

Вывод результатов на экран организован так, чтобы на экране номера мест, занятых командами, названия команд и набранные очки выводились в три ровных столбца. Названия разных команд имеют разную длину. Самое длинное название у команды ТОРПЕДО- МЕТАЛЛУРГ состоит из 17 символов. Для выравнивания длин строк каждое название дополняется пробелами до 18 символов. Число добавляемых пробелов вычисляется так:

18-length(Team[I])

Здесь length () — это стандартная функция, вычисляющая длину строки (число символов), указанной в скобках. Например, для ЦСКА длина строки равна 4, а для ТОРПЕДО-МЕТАЛЛУРГ длина равна 17. Значит, к ЦСКА добавится 14 пробелов, а к ТОРПЕДО-МЕТАЛЛУРГ — 1 пробел.

В операторе Team[I]:= Team[I] + ' '; используется операция «+» присоединения символов. В данном случае присоединяется пробел. К строке Team[I] добавится столько пробелов, сколько раз повторится присоединение. После этого по команде

Writeln(I:2,' ',Team[I]:18, B[I]:2)

в ровные колонки выведутся места, названия команд и очки. Результаты будут иметь на экране следующий вид:

1 ЦСКА 5 9

2 ЗЕНИТ 56

3 РУБИН 53

…………….

14 ТОРПЕДО-МЕТАЛЛУРГ 2 9

15 УРАЛАН 28

16 ЧЕРНОМОРЕЦ 24

 

 

Коротко о главном

 

Метод пузырька — алгоритм сортировки числового массива.

Структура алгоритма метода пузырька — два вложенных цикла с переменной длиной внутреннего цикла.

length() — функция определения длины строковой переменной.

В Паскале существует операция присоединения строк. Ее знак — «+».

 

Вопросы и задания

 

1. Как пояснить название метода сортировки массива — «метод пузырька»?

2. Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?

3. Введите в компьютер программу Premier_liga_2.

а) Выполните ее, получите результаты. Сравните с результатами, приведенными в параграфе.

б) Внесите изменения в программу для того, чтобы получить список в обратном порядке (по возрастанию очков). Выполните программу.

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

4. Если несколько команд набрали одинаковое количество очков, то места между ними распределяются по разнице забитых и пропущенных мячей: чем разница больше, тем место выше. Попробуйте усовершенствовать программу, учитывая это правило. Для этого в программу надо добавить массив с разницами мячей. Придумайте тест, на котором можно проверить работу программы.

5. Условие то же, что и в предыдущем задании. Но в качестве исходных данных вводится еще два массива: с числом забитых и пропущенных мячей каждой командой.

 

ЕК ЦОР: часть 2, заключение, § 6.2. ЦОР № 6.

 

Чему вы должны научиться, изучив главу II

 

• Строить несложные вычислительные алгоритмы с использованием блок-схем и Алгоритмического языка.

• Выполнять трассировку алгоритмов.

• Составлять программу на Паскале по данному алгоритму.

• Работать с системой программирования на Паскале: набирать текст программы; сохранять программу на диске и вызывать ее с диска; компилировать и исполнять программу; исправлять ошибки в программе.