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

- самый естественный, он же самый медленный алгоритм сортировки.

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

Количество проходов алгоритма пузырьковой сортировки в худшем случае будет равно количеству элементов в массиве. Поэтому наиболее просто (и наиболее затратно по времени) псевдокод алгоритма сортировки пузырьком можно составить так:

Процедура BoobleSort(A: массив, min - начальный индекс, max - конечный индекс);
Начало
цикл для j от min до max
цикл для i от min до max-1
если Ai больше чем Ai+1 то:
1. обменять местами Ai и Ai+1
Конец процедуры

Однако, если засекать событие обмена элементов местами (событие сортировки), то алгоритм пузырьковой сортировки можно несколько улучшить:

Процедура BoobleSort(A: массив, min - начальный индекс, max - конечный индекс);
Начало
sort = истина
цикл пока sort=истина
sort = ложь
цикл для i от min до max-1
если Ai больше чем Ai+1 то:
1. обменять местами Ai и Ai+1
2. sort = истина //Признак события сортировки
Конец процедуры

Проходы, меняющие местами элементы, производятся до тех пор, пока происходит событие сортировки - обмен местами элементов массива. Но даже когда все элементы уже выстроены по порядку, процедура не знает этого, и вынуждена сделать ещё один проход, на котором обменов уже не будет.

Если присмотреться к поведению алгоритма, то можно ещё улучшить алгоритм пузырьковой сортировки. Можно заметить, что если массив просматривается с начала, то максимальное число в массиве после первого же прохода сразу оказывается в конце массива, то есть на своём месте. На следующем проходе своё место занимает второе по величине число, и так далее. То есть на каждом очередном проходе нет необходимости просматривать массив до конца, а максимум до элемента с индексом max-n, где n - количество уже завершённых проходов. В результате, псевдокод улучшенной пузырьковой сортировки выглядит так:
Процедура BoobleSort(A: массив, min - начальный индекс, max - конечный индекс);
Начало
sort = истина
n = 0
цикл пока sort=истина
sort = ложь
цикл для i от min до max-1-n
если Ai больше чем Ai+1 то:
1. обменять местами Ai и Ai+1
2. sort = истина //Признак события сортировки
n = n+1
Конец процедуры

Небольшая модификация алгоритма, связанная со слежением за индексом последнего переставленного на каждом проходе элемента, может более точно определить наибольший индекс ещё нуждающихся в перестановках элементов - предоставлю это читателям!
Реализация алгоритма пузырьковой сортировки в Delphi может выглядеть следующим образом:
type TArray: Array of Integer; //Параметры массива нужно определить до вызова процедуры
procedure booblesort(var A: TArray; min, max: Integer);
var i, tmp, n: Integer;
Sort: Boolean;
begin
Sort: =True;
n: =0;
while Sort do
begin
Sort: =False;
for i: =min to max-1-n do
if A[i]> A[i+1] then
begin
Sort: =True;
tmp: =A[i]; A[i]: =A[i+1]; A[i+1]: =tmp;
end;
n: =n+1;
end;
end;

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