Самым простым методом сортировки является так называемый метод "пузырька". Предположим, что записи, подлежащие сортировке, хранятся в массиве, расположенном вертикально. Записи с малыми значениями ключевого поля более "легкие" и "всплывают" вверх наподобие пузырька. При первом проходе вдоль массива, начиная проход снизу, берется первая запись массива, и ее ключ поочередно сравнивается с ключами последующих записей. Если встречается запись с более "тяжелым" ключом, то эти записи меняются местами. При встрече с записью с более "легким" ключом эта запись становится "эталоном" для сравнения, и все последующие записи сравниваются с этим новым, более "легким" ключом. В результате запись с наименьшим значением ключа окажется в самом верху массива. Во время второго прохода вдоль массива находится запись со вторым по величине ключом, которая помещается под записью, найденной при первом проходе массива, т.е. на вторую сверху позицию, и т.д. Отметим, что во время второго и последующих проходов вдоль массива нет необходимости просматривать записи, найденные за предыдущие проходы, так как они имеют ключи, меньшие, чем у оставшихся записей. Другими словами, во время i-гo прохода не проверяются записи, стоящие на позициях выше i. В листинге 1 приведен описываемый алгоритм, в котором через А обозначен массив из n записей (тип данных rеcordtype). Здесь и далее предполагаем, что одно из полей записей называется key (ключ) и содержит значения ключей.
|
|
Листинг 1. Алгоритм „пузырька"
temp: recordtype;
for i:= n-1 downto 1 do
for j:= 2 to i + 1 do
if A[j].key < A[j - 1].key then
Begin
temp:= A[j];
A[j]:= A[j-1];
A[j-1]:= temp;
end;
Пример 7.1. В табл.5 приведены годы знаменитых извержений вулканов.
Таблица 5. Значения годов знаменитых извержений вулканов
i | начальное положение | 1-й проход | 2-й проход | 3-й проход | 4-й проход | 5-й проход |
1902 | ||||||
79 | ||||||
1883 | 79 | |||||
79 | ||||||
79 | ||||||
79 | ||||||
i | i = 6 | i = 5 | i = 4 | i = 3 | i = 2 | i = 1 |
Применим алгоритм "пузырька" для упорядочивания списка годов извержений вулканов в возрастающем порядке их значения, считая, что отношением линейного порядка в данном случае является отношение порядка ”<” над полем ключей. В табл. 2 показаны пять проходов алгоритма (в данном случае n = 6). Линии указывают позицию, выше которой записи уже упорядочены. После пятого прохода все записи, кроме последней, стоят на нужных местах, но последняя запись не случайно оказалась последней — она также уже стоит на нужном месте. Поэтому сортировка заканчивается.
|
|
Задача 7.10. Дан целочисленный массив размерностью 10 элементов. Упорядочить элементы данного массива по возрастанию методом «пузырька».
Вариант №1. Осуществим сортировку элементов массива по возрастанию, где пары стоящих элементов просматриваются снизу вверх.
Листинг программы
program task1;
uses crt;
const n = 10;
type vector = array [1..n] of integer;
var
a: Vector;
b, t, j: integer;
temp: integer;
begin
clrscr;
{формирование элементов массива случайным образом}
randomize;
for i:=1 to n do
begin
a[i]:= random(11)-5;
writeln ('a[', i, ']=', a[i]:3);
end;
{сортировка элементов массива по возрастанию}
b:= n;
while (b>0) do
begin
t:= 0;
for j:= 1 to b-1 do
begin
if (a[j] >a [j+1]) and (a[j] <> a[j+1]) then
begin
temp:= a[j];
a[j]:= a[j+1];
a[j+1]:= temp;
t:= j;
end; {оператора if}
end; {оператора for}
b:= t;
end; {оператора while}
{вывод упорядоченного массива на экран}
writeln ('Отсортированный массив по возрастанию');
for i:= 1 to n do
writeln ('a[', i, ']=', a[i]:3);
readln;
end.
Вариант №2. Осуществим сортировку элементов массива по возрастанию, где пары стоящих элементов просматриваются сверху вниз.
Листинг программы
program task1;
uses crt;
const n = 10;
type vector = array [1..n] of integer;
var
a: Vector;
i, j: integer;
temp: integer;
begin
clrscr;
{формирование элементов массива случайным образом}
randomize;
for i:=1 to n do
begin
a[i]:= random(11)-5;
writeln ('a[', i, ']=', a[i]:3);
end;
{сортировка элементов массива по возрастанию}
for i:= n-1 downto 1 do
begin
for j:= 2 to i+1 do
begin
if a[j] < a[j-1] then
begin
temp:= a[j];
a[j]:= a[j-1];
a[j-1]:= temp;
end;
end;
end;
{вывод упорядоченного массива на экран}
writeln ('Отсортированный массив по возрастанию');
for i:= 1 to n do
writeln ('a[', i, ']=', a[i]:3);
readln;
end.