Сортування бульбашкою

5.1 Визначення сортування бульбашкою

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

Принцип роботи:

1. Алгоритм проходить по списку і порівнює кожну пару сусідніх елементів.
2. Якщо елементи знаходяться в неправильному порядку (перший більший за другий для сортування за зростанням) — вони змінюються місцями.
3. Цей процес повторюється для всіх пар елементів у списку.
4. Після кожного повного проходу найбільший елемент «вспливає» на своє місце (як бульбашка на поверхні води), і тому він більше не бере участі в наступних проходах.
5. Процес повторюється доти, поки список не буде відсортовано.

Часова та просторова складність сортування бульбашкою

Часова складність:

• У найгіршому випадку: O(n^2) — відбувається, коли елементи спочатку впорядковані у зворотному порядку.
• У середньому випадку: O(n^2) — відбувається для випадкового розташування елементів.
• У найкращому випадку: O(n) — відбувається, коли елементи вже відсортовані (алгоритм може бути оптимізований для цього випадку, додавши перевірку, чи відбувся обмін елементів за прохід).

Просторова складність:

O(1) — оскільки алгоритм використовує постійну кількість додаткової пам'яті (тільки кілька змінних для зберігання тимчасових значень).

5.2 Реалізація алгоритму

Алгоритм «сортування бульбашкою» — це найпростіший і примітивний алгоритм сортування списку/масиву елементів. Він просто попарно порівнює елементи і змінює їх місцями, якщо потрібно.

Версія 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Обмін елементів
        

Внутрішній цикл (виділено зеленим) порівнює елемент з його сусідом справа. І якщо потрібно — змінює елементи місцями.

Версія 2:

В наш алгоритм відразу можна додати оптимізацію: після першого проходу алгоритму, наймаксимальніший елемент виявиться крайнім справа, тому його можна вже не враховувати при наступному циклі.

Після другої ітерації справа буде вже 2 максимальних елементи, тому внутрішній цикл можна вести не до n - 1, а до n - 1 - i. Де i — це кількість пройдених ітерацій зовнішнього циклу.

Новий варіант буде виглядати так:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Обмін елементів
        

Версія 3:

Також масив вже може бути майже відсортований. Тому можна додати таку оптимізацію: якщо внутрішній цикл пройшовся по всіх елементах, але не зробив жодного обміну, то сортування закінчено.

У цій версії використовується змінна swapped, яка відстежує, чи відбувся обмін елементів під час останнього проходу. Якщо після проходу по масиву жодного обміну не відбулося, це означає, що масив вже відсортований, і виконання подальших ітерацій безглуздо — вони не покращать сортування. Таким чином, змінна swapped дозволяє значно прискорити роботу алгоритму на майже відсортованих масивах, завершивши його виконання достроково.

Реалізація сортування бульбашкою на Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False # Оптимізація: перевірка, чи відбувся обмін
        for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Обмін елементів
                swapped = True
        if not swapped:
            break  # Якщо обмінів не було, масив вже відсортований
        
# Приклад використання:
array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(array)
print("Відсортований масив:", array)