Przejdź do treści

Sortowanie koktajlowe

Sortowanie koktajlowe, znane również jako sortowanie bąbelkowe z wstrząsami (ang. Cocktail Shaker Sort) lub sortowanie bidirectionalne, to odmiana algorytmu sortowania bąbelkowego. Podobnie jak sortowanie bąbelkowe, sortowanie koktajlowe jest prostym algorytmem, ale niezbyt wydajnym dla dużych zbiorów danych.

Algorytm sortowania koktajlowego różni się od sortowania bąbelkowego tym, że przegląda listę w obu kierunkach. Oznacza to, że podczas jednego przejścia lista jest przeglądana od początku do końca, a następnie od końca do początku. Proces ten powtarza się, aż do momentu, gdy cała zostanie jest posortowana.

Algorytm sortowania koktajlowego opiera się na następujących krokach:

  • Przeglądanie listy: przeglądamy listę od początku do końca, porównując sąsiednie elementy. Jeżeli są w niewłaściwej kolejności, zamieniamy je miejscami.
  • Przeglądanie listy w drugą stronę: teraz przeglądamy listę od końca do początku, ponownie porównując sąsiednie elementy i zamieniając je miejscami, jeśli są w niewłaściwej kolejności.
  • Powtarzanie: powtarzamy powyższe kroki, aż cała lista będzie posortowana.

Poniżej znajdziesz animację przedstawiającą ideę omawianego algorytmu.

Animacja

Sortowanie koktajlowe

Rozwiązanie

Pseudokod

procedura SortowanieKoktajlowe(n, A):
    1. Od i := 1 do n div 2, wykonuj:
        2. Od j := i do n - i, wykonuj:
            3. Jeżeli A[j] > A[j + 1], to:
                4. Zamień(A[j], A[j + 1])
        5. Od j := n - i w dół do i + 1, wykonuj:
            6. Jeżeli A[j] < A[j - 1], to:
                7. Zamień(A[j], A[j - 1]

Info

div oznacza dzielenie całkowite

Schemat blokowy

%%{init: {"flowchart": {"curve": "linear"}, "theme": "neutral"} }%%
flowchart TD
    START(["SortowanieKoktajlowe(n, A)"]) --> K0[i := 1]
    K0 --> K1{i <= n div 2}
    K1 -- PRAWDA --> K2p[j := i]
    K2p --> K2{j <= n - i}
    K2 -- PRAWDA --> K3{"A[j] > A[j + 1]"}
    K3 -- PRAWDA --> K4["Zamień(A[j], A[j + 1])"]
    K3 -- FAŁSZ --> K2i[j := j + 1]
    K4 --> K2i
    K2i --> K2
    K2 --> K5p[j := n - i]
    K5p --> K5{j >= i + 1}
    K5 -- PRAWDA --> K6{"A[j] < A[j - 1]"}
    K6 -- PRAWDA --> K7["Zamień(A[j], A[j - 1])"]
    K6 -- FAŁSZ --> K5i[j := j - 1]
    K7 --> K5i
    K5i --> K5
    K5 -- FAŁSZ --> K1i[i := i + 1]
    K1i --> K1
    K1 -- FAŁSZ --------> STOP([STOP])

Złożoność

Podobnie jak sortowanie bąbelkowe, sortowanie koktajlowe ma złożoność obliczeniową \(O(n^2)\) zarówno w przypadku średnim, jak i najgorszym. Wynika to z przeglądania całej listy dla każdego elementu.

Implementacja

C++

Python

Kotlin