Як реалізується сортування бульбашкою?

Сортування бульбашкою (Bubble Sort) є одним з найпростіших алгоритмів сортування. Його ідея полягає в порівнянні сусідніх елементів масиву і обміні їх місцями, якщо вони не відсортовані за потрібним порядком. При кожному проходженні масиву найбільший елемент "спливає" на поверхню, тому алгоритм називається "бульбашкою".

Основний алгоритм сортування бульбашкою можна описати таким чином:

1. Пройти по масиву з початку до кінця.
2. Порівняти два сусідніх елементи.
3. Якщо вони не відсортовані, обміняти їх місцями.
4. Продовжити прохід до кінця масиву.
5. Якщо на поточному проході не було обмінів, значить масив відсортований і можна зупинитись.

Цей алгоритм повторюється доти, доки весь масив не буде відсортований. Його складність становить O(n^2), що робить його неефективним для великих масивів.

Реалізація алгоритму сортування бульбашкою в коді може виглядати таким чином:

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

У цьому прикладі ми використовуємо два вкладені цикли for, щоб пройтись по масиву і порівняти сусідні елементи. Ми обмінюємо елементи місцями, якщо вони не відсортовані, і