УП_САОД_2003

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

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

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

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

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

procedure BubleSort(n: integer;

var A: array[1..n] of integer);

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

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;

Рисунок 45. Сортировка методом пузырька

Этот алгоритм имеет среднюю и максимальную временные сложности, пропорциональную O(n²) (два вложенных цикла, зависящих от n линейно) и не требует дополнительной памяти. Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к O(n). Также следует отметить, что данный алгоритм не требует дополнительной памяти и сохраняет порядок элементов с одинаковыми значениями.

Содержание