все Python 3Алгоритмы и структуры данныхпонятие

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

сортировка

O(n²). Сравнивает соседние элементы и меняет местами. Наглядна, но медленна. Оптимизация — флаг обмена.

Синтаксис

def bubble_sort(arr):

В рабочем коде пузырёк не пишут: sorted() и list.sort() используют Timsort на C с O(n log n), и уже на нескольких тысячах элементов разрыв становится неприличным — пузырёк живёт только как учебный разбор. Две ошибки повторяются постоянно: во внутреннем цикле забывают -i-1 (лишние проходы по уже отсортированному хвосту либо выход за границу при обращении к j+1) и не замечают, что обмен идёт на месте — список вызывающего меняется, даже если функция ничего не вернула.

Примеры

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
print(bubble_sort([64,34,25,12,22,11,90]))  # → [11,12,22,25,34,64,90]
# С флагом (оптимизация)
def bubble_opt(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, 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  # уже отсортирован
    return arr
print(bubble_opt([1,2,3,4,5]))  # → [1,2,3,4,5] (1 проход)
# Трассировка
def bubble_trace(arr):
    arr = arr[:]
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
        print(f'pass {i+1}: {arr}')
    return arr
bubble_trace([5,3,1,4,2])
# → pass 1: [3,1,4,2,5] / pass 2: [1,3,2,4,5] ...
# Число обменов
def bubble_count(arr):
    arr = arr[:]
    n = len(arr); swaps = 0
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swaps += 1
    return arr, swaps
print(bubble_count([3,2,1]))  # → ([1,2,3], 3)
# Worst case: обратно отсортированный
import time
arr = list(range(1000, 0, -1))
t = time.time()
bubble_sort(arr[:])
print(f'Bubble sort 1000 elements: {time.time()-t:.3f}s')

См. также

Открыть в полном глоссарииdocs.python.orgСообщить о неточности