Сортировка пузырьком: алгоритм, примеры, преимущества

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

Процесс сортировки пузырьком можно представить следующим образом:

1. Проходим по массиву и сравниваем каждый элемент с его соседним.
2. Если текущий элемент больше следующего, меняем их местами. Это делается для каждой пары элементов на протяжении всего массива.
3. Повторяем шаги 1 и 2 до тех пор, пока в проходе по массиву не потребуется ни одного обмена элементов. Это означает, что массив уже отсортирован.

Давайте представим сортировку пузырьком на примере массива integer чисел:

def bubble_sort(arr):
    n = len(arr)
    swapped = True
    while swapped:
        swapped = False
        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        n -= 1
    return arr

# Пример использования
arr = [5, 2, 9, 1, 7]
sorted_arr = bubble_sort(arr)
print(sorted_arr)  # Вывод: [1, 2, 5, 7, 9]

В данном примере функция bubble_sort принимает массив arr в качестве аргумента и возвращает отсортированный массив. Переменная n устанавливается равной длине массива и используется как ограничение в цикле while. Переменная swapped позволяет определить, происходили ли обмены элементов на текущей итерации. Если за проход по массиву не происходит ни одного обмена, массив уже отсортирован и цикл while завершается.

На каждой итерации цикла for, сравниваются пары элементов. Если текущий элемент больше следующего, они меняются местами с помощью оператора присваивания. Затем переменная swapped устанавливается в значение True, чтобы указать на произошедший обмен элементов.

Цикл for повторяется до тех пор, пока не достигнут последний элемент массива (n - 1), а затем значение переменной n уменьшается на 1. Это связано с тем, что самый большой элемент уже "всплыл" на последнюю позицию, и на следующих итерациях не нужно проводить сравнения для него.

В итоге получаем отсортированный массив [1, 2, 5, 7, 9].

Сортировка пузырьком является простым и понятным алгоритмом, но его эффективность ограничена. В случае больших массивов или массивов с большим количеством неотсортированных элементов, этот алгоритм может быть слишком медленным. Это объясняется тем, что он имеет квадратичную сложность O(n^2), где n - количество элементов в массиве.