Przykład działania sortowania koktajlowego | |
| Rodzaj | |
|---|---|
| Struktura danych | |
| Złożoność | |
| Czasowa | |
| Pamięciowa | |
Sortowanie koktajlowe, znane także jako dwukierunkowe sortowanie bąbelkowe i sortowanie przez wstrząsanie (które również odwołuje się do odmiany sortowania przez wybieranie) – odmiana sortowania bąbelkowego, które jest stabilnym algorytmem sortowania sortującym za pomocą porównań. Algorytm w przeciwieństwie do sortowania bąbelkowego sortuje liczby w zbiorze w dwóch kierunkach.
Sortowanie koktajlowe oparte jest na spostrzeżeniu, iż każdy obieg wewnętrznej pętli sortującej umieszcza na właściwym miejscu element najstarszy, a elementy młodsze przesuwa o 1 pozycję w kierunku początku zbioru. Jeśli pętla ta zostanie wykonana w kierunku odwrotnym, to wtedy najmłodszy element znajdzie się na swoim właściwym miejscu, a elementy starsze przesuną się o jedną pozycję w kierunku końca zbioru. Łącząc te dwie pętle sortując wewnętrznie naprzemiennie w kierunku normalnym i odwrotnym, otrzymujemy algorytm sortowania koktajlowego.
Przykład implementacji algorytmu w pseudojęzyku:
function cocktail_sort(list, list_length) // pierwszy element zbioru ma indeks 0 { bottom = 0; top = list_length - 1; zamiana = true; while(zamiana == true) // jeżeli żaden element nie został zamieniony, lista jest posortowana { zamiana = false; for(i = bottom; i < top; i = i + 1) { if(list[i] > list[i + 1]) // sprawdzamy czy elementy są na właściwych miejscach { zamien(list[i], list[i + 1]); // zamieniamy elementy miejscami zamiana = true; } } // zmniejszamy wartość `top` ponieważ element o największej wartości jest posortowany top = top - 1; for(i = top; i > bottom; i = i - 1) { if(list[i] < list[i - 1]) { zamien(list[i], list[i - 1]); zamiana = true; } } // zwiększamy wartość `bottom` ponieważ element o najmniejszej wartości jest posortowany bottom = bottom + 1; } }
Sortowanie koktajlowe jest odmianą sortowania bąbelkowego. Różni się od niego tym, że zamiast wielokrotnie przechodzić przez listę od dołu do góry przechodzi na przemian z dołu do góry i następnie z góry do dołu. Dzięki temu ma trochę lepsze osiągi niż standardowe sortowanie bąbelkowe. Wynika to z tego że sortowanie bąbelkowe przechodzi przez listę tylko w jednym kierunku, zatem może cofać się jedynie o jedną pozycję bez możliwości powtarzania.
Np. posortowanie elementów (2,3,4,5,1) metoda koktajlową wymaga tylko jednego przejścia aby elementy zostały posortowane, zaś jeśli użyjemy metody bąbelkowej, będziemy potrzebowali czterech przejść.
Typowa czasowa złożoność obliczeniowa sortowania koktajlowego jest klasy jednak przy sortowaniu zbiorów w znacznym stopniu posortowanych klasa złożoności obliczeniowej redukuje się do