Сортировка пузырьком с на примерах

Как работает сортировка пузырьком и как ее реализовать на языке программирования?

Сортировка пузырьком (Bubble sort) является простым алгоритмом сортировки, который позволяет упорядочить элементы в массиве по возрастанию или убыванию. Он получил свое название благодаря тому, что наибольший или наименьший элемент каждый раз "всплывает" на нужную позицию, как пузырек в воде.

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

Пример реализации сортировки пузырьком на языке Python:

python
def bubble_sort(arr):
    n = len(arr)
    # Проходим по массиву n-1 раз,
    # т.к. после каждого прохода максимальный элемент оказывается на своем месте
    for i in range(n - 1):
        # Проходим по оставшейся части массива
        for j in range(n - i - 1):
            # Сравниваем пару соседних элементов
            if arr[j] > arr[j + 1]:
                # Если левый элемент больше правого, меняем их местами
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Тестирование функции:

python
arr = [5, 2, 8, 3, 1, 7, 4, 6]
sorted_arr = bubble_sort(arr)
print(sorted_arr)  # [1, 2, 3, 4, 5, 6, 7, 8]

Также можно реализовать сортировку пузырьком с флагом, который показывает, было ли выполнено перестановка на текущем проходе массива. Если перестановок не было, значит, массив уже отсортирован, и можно выйти из цикла.

python
def bubble_sort_flag(arr):
    n = len(arr)
    for i in range(n - 1):
        # Изначально флаг False, т.к. перестановок нет
        is_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]
                is_swapped = True
        # Если перестановок нет, выходим из цикла
        if not is_swapped:
            break
    return arr