Временная сложность
Худший и средний случай: O(n^2), где n — количество элементов в массиве. Когда массив полностью не отсортирован;
Лучший случай: O(n), когда массив уже отсортирован, и алгоритм завершает работу после первого прохода.
Пространственная сложность
O(1), так как сортировка пузырьком является алгоритмом сортировки на месте (in-place sorting) и не требует дополнительного хранения данных кроме исходного массива.
Идея
Повторно проходим по массиву, сравниваем соседние элементы и меняем их местами, если они в неправильном порядке. Процесс повторяется до тех пор, пока массив не будет отсортирован.
Функция sort
1. Определяем размер массива n. Если размер меньше или равен 1, возвращаем массив, так как он уже отсортирован.
2. Используем переменную swapped, чтобы отслеживать, были ли выполнены обмены во время прохода по массиву.
3. Осуществляем проход по массиву, сравниваем каждую пару соседних элементов. Если элементы находятся в неправильном порядке, меняем их местами.
4. Если после прохода по массиву не было сделано ни одного обмена, массив считается отсортированным, и алгоритм завершает работу.
5. Повторяем проходы, пока массив не будет полностью отсортирован.
Функция swap
Меняем местами два элемента массива, используя временную переменную.
Польза такой сортировки
Обычно не используется для практических приложений из-за своей низкой эффективности на больших списках, но есть ряд особенностей:
1. Легко понять и реализовать, даже для начинающих программистов.
2. Не требует дополнительного пространства для хранения данных (in-place sorting)
3. Сохраняет относительный порядок равных элементов (стабильная сортировка)
4. Можно быстро определить, что массив уже отсортирован, и завершить выполнение.
5. Может быть полезной для небольших или частично отсортированных массивов.