🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
🤔 Какая сложность у пузырьковой сортировки?
Пузырьковая сортировка (Bubble Sort) — это один из самых простых, но неэффективных алгоритмов сортировки.
🚩Как работает пузырьковая сортировка?
1. Проходим по массиву несколько раз.
2. На каждой итерации сравниваем соседние элементы и меняем их местами, если они идут не в том порядке.
3. После первого прохода наибольший элемент оказывается в конце массива.
4. Повторяем процесс, пока массив не отсортируется.
🚩Рассчёт сложности (`O(n²)`)
Количество сравнений в худшем случае:
- На первой итерации: n-1 сравнений
- На второй: n-2 сравнений
- На третьей: n-3 сравнений
- …
- Всего: (n-1) + (n-2) + ... + 1 = O(n²)
Количество обменов (swap) в худшем случае:
- Если массив полностью перевёрнут, на каждой итерации будет максимальное количество перестановок → O(n²).
🚩Оптимизированная пузырьковая сортировка (`O(n)`)
Если на проходе по массиву не было перестановок, значит массив уже отсортирован.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False # Флаг, отслеживающий перестановки
for j in range(n - i - 1):
if arr[j] > arr[j + 1]: # Если элементы в неправильном порядке, меняем местами
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break # Если перестановок не было, завершаем сортировку
arr = [1, 2, 3, 4, 5] # Уже отсортированный массив
bubble_sort(arr)
print(arr) # [1, 2, 3, 4, 5]
Ставь 👍 и забирай 📚 Базу знаний