Задачи / Сортировки / Сортировка пузырьком

Сортировка пузырьком: блок-схема и алгоритм

Проходим по массиву и сравниваем соседние элементы: если левый больше правого, меняем их местами. За один проход самый большой элемент «всплывает» в конец, как пузырёк. После n − 1 проходов массив отсортирован.

Алгоритм по шагам

Ввести n и массив a.
Внешний цикл: проход i от 1 до n − 1.
Внутренний цикл: j от 1 до n − i (последние i − 1 элементов уже на своих местах).
Если a[j] > a[j + 1], поменять их местами через переменную t.
Вывести отсортированный массив.

Открыть блок-схему в редакторе

Пример работы

Вход	a = [5, 1, 4, 2]
Шаг 1	Проход 1: [1, 5, 4, 2] → [1, 4, 5, 2] → [1, 4, 2, 5] — 5 на месте
Шаг 2	Проход 2: [1, 4, 2, 5] → [1, 2, 4, 5] — 4 на месте
Шаг 3	Проход 3: обменов нет
Результат	1 2 4 5

Решение на Python

n = int(input())
a = list(map(int, input().split()))
for i in range(n - 1):
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
print(*a)

Решение на Pascal

var a: array[1..100] of integer;
    n, i, j, t: integer;
begin
  readln(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
        t := a[j];
        a[j] := a[j + 1];
        a[j + 1] := t;
      end;
  for i := 1 to n do write(a[i], ' ');
end.

Код блок-схемы

Схема выше нарисована по этому псевдокоду. Скопируйте его в редактор блок-схем или нажмите «Открыть блок-схему в редакторе».

блок-схема: Сортировка пузырьком
начало
ввод n, массив a[1..n]
для i от 1 до n − 1
    для j от 1 до n − i
        если a[j] > a[j + 1]
            t = a[j]
            a[j] = a[j + 1]
            a[j + 1] = t
вывод массив a
конец

Сложность

O(n²) сравнений в худшем и среднем случае, память O(1). Сортировка устойчивая: равные элементы не меняются местами.

Частые ошибки

Внутренний цикл до n, а не до n − i: обращение к a[n + 1] за пределами массива.
Обмен без временной переменной.
Можно ускорить: если за проход не было ни одного обмена, массив уже отсортирован и цикл можно прервать.