Sortowanie bąbelkowe

5.1 Definicja sortowania bąbelkowego

Sortowanie bąbelkowe (Bubble Sort) — to prosty algorytm sortowania, który wielokrotnie przechodzi przez listę, porównując sąsiednie elementy i zamieniając je miejscami, jeśli są w złej kolejności. Ten proces trwa do momentu, aż lista będzie w pełni posortowana.

Zasada działania:

1. Algorytm przechodzi przez listę i porównuje każdą parę sąsiednich elementów.
2. Jeśli elementy są w złej kolejności (pierwszy większy od drugiego dla sortowania rosnącego) — są zamieniane miejscami.
3. Ten proces jest powtarzany dla wszystkich par elementów na liście.
4. Po każdym pełnym przejściu największy element „wypływa” na swoje miejsce (jak bąbel na powierzchni wody), i dlatego nie bierze już udziału w kolejnych przejściach.
5. Proces trwa, aż lista zostanie posortowana.

Złożoność czasowa i przestrzenna sortowania bąbelkowego

Złożoność czasowa:

• W najgorszym wypadku: O(n^2) — występuje, gdy elementy są początkowo uporządkowane w odwrotnej kolejności.
• W średnim wypadku: O(n^2) — występuje dla losowego rozmieszczenia elementów.
• W najlepszym wypadku: O(n) — występuje, gdy elementy są już posortowane (algorytm można zoptymalizować dla tego przypadku, dodając sprawdzenie, czy nastąpiła zamiana elementów w czasie przejścia).

Złożoność przestrzenna:

O(1) — ponieważ algorytm używa stałej ilości dodatkowej pamięci (tylko kilka zmiennych do przechowywania wartości tymczasowych).

5.2 Implementacja algorytmu

Algorytm „sortowania bąbelkowego” — to najprostszy i najbardziej prymitywny algorytm sortowania listy/array elementów. Po prostu porównuje elementy parami i zamienia je miejscami, jeśli trzeba.

Wersja 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]  # Wymiana elementów

print("Posortowana tablica:", array)
# Wyjście: Posortowana tablica: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Wewnętrzna pętla (wyróżniona na zielono) porównuje element z jego sąsiadem po prawej. I jeśli trzeba — zamienia elementy miejscami.

Wersja 2:

Do naszego algorytmu można od razu dodać optymalizację: po pierwszym przejściu algorytmu największy element znajdzie się na końcu, więc nie można go już uwzględniać w kolejnej pętli.

Po drugiej iteracji z prawej strony będą już 2 największe elementy, więc wewnętrzną pętlę można prowadzić nie do n - 1, ale do n - 1 - i. Gdzie i — to liczba wykonanych iteracji zewnętrznej pętli.

Nowy wariant będzie wyglądał tak:

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]  # Wymiana elementów

print("Posortowana tablica:", array)
# Wyjście: Posortowana tablica: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Wersja 3:

Również tablica może być już prawie posortowana. Dlatego można dodać taką optymalizację: jeśli wewnętrzna pętla przeszła przez wszystkie elementy, ale nie wykonała żadnej wymiany, to sortowanie jest zakończone.

W tej wersji używa się zmiennej swapped, która śledzi, czy doszło do wymiany elementów podczas ostatniego przejścia. Jeśli po przejściu przez tablicę nie nastąpiła żadna wymiana, oznacza to, że tablica jest już posortowana i dalsze iteracje są bezcelowe — nie poprawią sortowania. W ten sposób zmienna swapped pozwala znacznie przyspieszyć działanie algorytmu na prawie posortowanych tablicach, kończąc jego wykonywanie wcześniej.

Implementacja sortowania bąbelkowego w Pythonie:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False # Optymalizacja: sprawdzenie, czy nastąpiła wymiana
        for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Wymiana elementów
                swapped = True
        if not swapped:
            break  # Jeśli nie było wymian, tablica jest już posortowana
    return array

# Przykład użycia:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Posortowana tablica:", sorted_array)
# Wyjście: Posortowana tablica: [11, 12, 22, 25, 34, 64, 90]