Алгоритм сортировки пузырьком
Сущность алгоритма заключается в следующем. Мы проходим по массиву и берем из него числа парами, вот так – первое число и второе, затем второе и третье, затем третье и четвертое и т.д. и если в очередной паре последнее число меньше первого, то меняем их местами.
Если за полный проход массива не было обнаружено ни одной неправильной пары, то массив, очевидно, упорядочен и работу можно прекратить. Если была обнаружена хотя бы одна неправильная пара, то массив может быть упорядочен, а может быть и нет, но во всяком случае еще один проход не помешает. Таким образом, алгоритм пузырька представляет собой два вложенных цикла, внешний запускает очередной проход, если была обнаружена неправильная пара, а внутренний просматривает пары чисел и выполняет перестановку если это необходимо.
Почему алгоритм называется «ПУЗЫРЕК»
Назовем конец массива дном, а начало поверхностью, числа с меньшим значением назовем легкими, а с большими – тяжелыми. Просчитайте несколько шагов ПУЗЫРЬКА и вы увидите, что легкие числа, как пузырьки всплывают к поверхности, оттого и алгоритм и назван ПУЗЫРЬКОМ.
Алгоритм
Флаг = МАССИВ НЕУПОРЯДОЧЕН
Пока Флаг = МАССИВ НЕУПОРЯДОЧЕН делать
§ Номер пары =1
§ Флаг = МАССИВ УПОРЯДОЧЕН
§ Пока Номер пары меньше количества элементов массива делать
o Взять очередную ПАРУ ЧИСЕЛ для анализа. ПАРА ЧИСЕЛ состоит из чисел с номерами равными (Номер пары, Номер пары +1)
o Если пара неправильная то
§ Поменять местами значения элементов ПАРЫ ЧИСЕЛ
§ Флаг = МАССИВ НЕУПОРЯДОЧЕН
Распечатать массив чисел
Текст программы:
MODULE example;
IMPORT In, StdLog;
PROCEDURE Sort*;
VAR
a:ARRAY 100 OF INTEGER;
N,i,k,c:INTEGER;
BEGIN
N:=-1;
In.Open;
REPEAT
N:=N+1;
In.Int(a[N]);
UNTIL ~In.Done;
FOR i:=0 TO N-2 DO
FOR k:=0 TO N-2-i DO
IF a[k]>a[k+1] THEN
c:=a[k];a[k]:=a[k+1];a[k+1]:=c;
END;
END;
END;
FOR i:=0 TO N-1 DO
StdLog.Int(a[i]);
END;
END Sort;
END example.