Сортировка пузырьком (Bubble Sort)

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

Сложность алгоритма сортировки пузырьком зависит от состояния входного массива:

1. Лучший случай: O(n)

• Это происходит, когда массив уже отсортирован. Алгоритм делает один проход по массиву и не выполняет ни одного обмена.

2. Средний случай: O(n²)

• В среднем, алгоритм будет выполнять множество обменов и сравнений, что приводит к квадратичной сложности.

3. Худший случай: O(n²)

• Это происходит, когда массив отсортирован в обратном порядке. Алгоритму нужно будет выполнить максимальное количество обменов.

Таким образом, общая временная сложность сортировки пузырьком — O(n²) в большинстве случаев, что делает его неэффективным для больших массивов по сравнению с более продвинутыми алгоритмами сортировки. Затраты по памяти O(1).

▎Пространственная сложность

O(1) - алгоритм сортирует массив "на месте".

▎Устойчивость:

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

Реализация сортировки на языке программирования C++:

Реализация сортировки на языке программирования Python: