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

Простейший алгоритм сортировки. Последовательно сравниваем соседние элементы и меняем их местами, если они стоят в неправильном порядке.

Идея алгоритма

Проходим массив слева направо, сравнивая пары соседних элементов
Если левый больше правого — меняем их местами
После каждого прохода самый большой элемент «всплывает» в конец (как пузырёк в воде)
Повторяем, каждый раз проверяя на один элемент меньше

Разбор

Внешний цикл

нц для i от 0 до n - 2
    ...
кц

Каждый проход «всплывает» один элемент на своё место. После $i$-го прохода последние $i$ элементов уже отсортированы. Нужно $n - 1$ проходов.

Внутренний цикл со сравнением

нц для j от 0 до n - 2 - i
    если A[j] > A[j + 1] то
        tmp := A[j]
        A[j] := A[j + 1]
        A[j + 1] := tmp
    все
кц

Сравниваем A[j] и A[j + 1] — два соседних элемента
Если левый больше — меняем местами через временную переменную tmp
Верхняя граница n - 2 - i: не проверяем уже отсортированный «хвост»

Вспомогательные функции

Программа использует две вспомогательные функции:

заполнить_случайными — заполняет массив случайными числами от 0 до 99
печать_массива — выводит элементы через пробел

Сложность: $O(n^2)$ — самый простой для понимания, но медленный на больших массивах.

Полная программа

алг main(цел n)
нач
    если n <= 0 то
        вывод "Размер массива должен быть положительным", нс
        выход
    все

    цел таб A[0:n-1]
    заполнить_случайными(n, A)

    вывод "Исходный массив:", нс
    печать_массива(n, A)

    bubblesort(n, A)

    вывод "Отсортированный массив:", нс
    печать_массива(n, A)
кон

алг bubblesort(цел n, цел таб A[0:n-1])
нач
    цел i, j, tmp
    нц для i от 0 до n - 2
        нц для j от 0 до n - 2 - i
            если A[j] > A[j + 1] то
                tmp := A[j]
                A[j] := A[j + 1]
                A[j + 1] := tmp
            все
        кц
    кц
кон

алг заполнить_случайными(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        A[i] := irnd(100)
    кц
кон

алг печать_массива(цел n, цел таб A[0:n-1])
нач
    цел i
    нц для i от 0 до n - 1
        вывод A[i], " "
    кц
    вывод нс
кон

▶ Запустить пример