ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 1

Тема: «Пузырьковая сортировка»

Цель: научиться использовать алгоритм пузырьковой сортировки для сортировки по возрастанию и убыванию одномерных массивов и массивов записей.

Ход работы

Теоретические обоснования

Сортировка – это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, ≥, ≤, =. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию. В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются рядом друг с другом в любом порядке.

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

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

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

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

Теперь запишем алгоритм:

{Заранее описываем пользовательский тип – одномерный массив}

Type mas= array[1..n] of integer;

…

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

{Параметрами процедуры являются n – размер массива, A – массив}

procedure BubleSort(n: integer; var A: mas);

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

var

i, j, Tmp: integer;

Flag: boolean;

begin

for i := n-1 downto 1 do begin

Flag := false;

for j := 1 to i do

if A[j] > A[j+1] then begin

Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp;

Flag := true;

end;

if not Flag then Break;

end;

end;

Пример сортировки одномерного массива, состоящего из 5 элементов:

Задание 1. Выполнить сортировку в одномерном массиве. Массив заполнить случайными числами, вывести исходный массив, выполнить сортировку методом пузырька, вывести отсортированный массив.

Задание 2. Дан массив записей, каждая запись описывается свойствами: фамилия, имя студента, год рождения. Выполнить сортировку в массиве записей по полю год рождения по возрастанию. Заполнить массив записей, вывести исходный массив в табличном виде, выполнить сортировку методом пузырька, вывести отсортированный массив в табличном виде.

Выполнение задания 1.

Рассмотрим решение задачи 2 способами.

1 способ. Без использования процедур.

uses crt;

{задаем тип – одномерный массив, который может состоять из 20 элементов}

type massiv=array[1..20] of integer;

{описываем переменные:

а – имя массива,

x, y – начало и конец диапазона для заполнения массива числами,

n – размер массива,

i – для работы с массивом,

j, tmp – для сортировки массива,

flag – логическая переменная, которая будет «следить» за тем, выполнялся ли обмен в массиве}

var a:massiv;

x,y,n,i,j,tmp:integer;

Flag: boolean;

begin

{очищаем экран}

clrscr;

writeln('введите кол-во элементов массива');

readln(n);

writeln('введите диапазон');

readln(x,y);

{подключение генератора случайных чисел, генерирование чисел происходит на отрезке от 0 до 1}

randomize;

writeln('исходный массив');

{заполняем массив случайными числами и выводим его}

for i:=1 to n do

begin

a[i]:=random(y-x)+x;

write(a[i]:3, ' ');

end;

writeln;

{выполняем сортировку методом пузырька}

for i := n-1 downto 1 do begin

Flag := false;

for j := 1 to i do

if A[j] > A[j+1] then begin

Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp;

Flag := true;

end;

if not Flag then Break;

end;

{ выводим результирующий массив}

writeln('отсортированный массив');

for i:=1 to n do

write(a[i]:3, ' ');

writeln;

readln;

end.

2 способ. С использованием процедур.

uses crt;

type massiv=array[1..20] of integer;

var a:massiv;

n,i:integer;

{процедура заполнения массива случайными числами}

procedure vvod(var n:integer; var a:massiv);

var x,y:integer;

begin

writeln('введите кол-во элементов массива');

readln(n);

writeln('введите диапазон');

readln(x,y);

randomize;

for i:=1 to n do

a[i]:=random(y-x)+x;

end;

{процедура вывода массива на экран}

procedure vivod(n:integer; var a:massiv);

begin

for i:=1 to n do

write(a[i]:3, ' ');

writeln;

end;

{процедура сортировки массива методом пузырька}

procedure sort(n:integer; var a:massiv);

var j,tmp:integer;

Flag: boolean;

begin

for i := n-1 downto 1 do begin

Flag := false;

for j := 1 to i do

if A[j] > A[j+1] then begin

Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp;

Flag := true;

end;

if not Flag then Break;

end;

end;

{основная программа}

begin

clrscr;

writeln('исходный массив');

{вызов процедуры заполнения массива}

vvod(n,a);

{вызов процедуры вывода массива на экран}

vivod(n,a);

writeln('отсортированный массив');

{вызов процедуры сортировки массива}

sort(n,a);

{вызов процедуры вывода массива на экран}

vivod(n,a);

writeln;

readln;

end.

Выполнение задания 2.

Рассмотрим решение задачи 2 способами.

1 способ. Без использования процедур.

uses CRT;

{описание пользовательского типа – запись с полями фамилия, имя и год рождения}

type student=record

fam,imya:string[15];

god:integer;

end;

{описание пользовательского типа – массив записей}

stud=array [1..20] of student;

{описание переменных

а – массив записей,

n – размер массива,

i,j – для организации циклов ввода и вывода с массива записей и сортировки массива

tmp – временная переменная для хранения текущих данных текущего студента – фамилии, имени, года рождения}

var a:stud;

i,j,n:integer;

tmp:student;

flag:boolean;

begin

clrscr;

write('Введите количество студентов: ');

readln(n);

{цикл заполнения массива записей}

for i:=1 to n do

Begin

Writeln('Введите информацию о ',i,'-ом студенте: ');

write('-фамилия: '); readln(a[i].fam);

write('-имя: '); readln(a[i].imya);

write('-год рождения: '); readln(a[i].god);

end;

clrscr;

write('Исходные данные: ');

Writeln(' Фамилия Имя Год рождения');

{цикл вывода массива записей в виде столбцов}

for i:=1 to n do

writeln(a[i].fam:15,' ',a[i].imya:15,' ',a[i].god:6);

{сортировка по полю год рождения}

for i := n-1 downto 1 do begin

Flag := false;

for j := 1 to i do

if A[j].god > A[j+1].god then begin

Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp;

Flag := true;

end;

if not Flag then Break;

end;

writeln('отсортированный массив');

Writeln(' Фамилия Имя Год рождения');

{выводим отсортированный массив записей на экран}

for i:=1 to n do

writeln(a[i].fam:15,' ',a[i].imya:15,' ',a[i].god:6);

readln;

end.

2 способ. С использованием процедур.

uses CRT;

type student=record

fam,imya:string[25];

god:integer;

end;

stud=array [1..20] of student;

var a:stud;

i,n:integer;

{процедура ввода данных о студентах}

procedure vvod(var n:integer; var a:stud);

begin

write('Введите количество студентов: ');

readln(n);

for i:=1 to n do

Begin

Writeln('Введите информацию о ',i,'-ом студенте: ');

write('-фамилия: '); readln(a[i].fam);

write('-имя: '); readln(a[i].imya);

write('-год рождения: '); readln(a[i].god);

end;

end;

{процедура вывода данных о студентах}

procedure vivod(n:integer; var a:stud);

begin

write('Исходные данные: ');

Writeln(' Фамилия Имя Год рождения');

for i:=1 to n do

writeln(a[i].fam:15,' ',a[i].imya:15,' ',a[i].god:6);

end;

{процедура сортировки по поля год рождения}

procedure sort(n:integer; var a:stud);

var j:integer;

tmp:student;

flag:boolean;

begin

for i := n-1 downto 1 do begin

Flag := false;

for j := 1 to i do

if A[j].god > A[j+1].god then begin

Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp;

Flag := true;

end;

if not Flag then Break;

end;

end;

begin

clrscr;

writeln('исходный массив');

{вызов процедуры ввода данных}

vvod(n,a);

{вызов процедуры вывода данных}

vivod(n,a);

writeln('отсортированный массив');

{вызов процедуры сортировки данных}

sort(n,a);

{вызов процедуры вывода}

vivod(n,a);

writeln;

readln;

end.

Задания для самостоятельного решения:

1. Выполните сортировку одномерного массива методом пузырька:

Заполнение, вывод массива и сортировку оформить в виде процедур

2. Выполнить сортировку массива записей методом пузырька:

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

Квартира описывается свойствами - порядковый номер квартиры в списке, количество комнат, площадь, этаж, стоимость.

Отсортируйте квартиры по стоимости.