олимпиадники-информатики

Сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, сортировка Шелла и быстрая сортировка.

Пример работа алгоритма



Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)



Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)



Теперь массив отсортирован и алгоритм может быть завершён.

Программный код

var a:array[1..10000] of integer;
	i,j,x,n:integer;
begin
  readln(n);  
  writeln('введите ',n,' элементов массива');
  for i:=1 to n do
   read( a[i] );
  for i:=1 to n-1 do
   for j:=1 to n-i do
	if a[j]>a[j+1] then begin
                 		x:=a[j];
                 		a[j]:=a[j+1];
                 		a[j+1]:=x;
                    	end;
writeln('после сортировки:');
for i:=1 to n do
  write( a[i],' ' );
end.