Sortowanie koktajlowe

Sortowanie koktajlowe, znane także jako dwukierunkowe sortowanie bąbelkowe, sortowanie przez wstrząsanie (które również odwołuje się do odmiany sortowania przez wybieranie), jest odmianą 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.

Opis algorytmu

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.

Kod źródłowy

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 nie 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 nieposortowany 
        bottom = bottom + 1;  
    }
}

Optymalizacja

Jedynym możliwym sposobem optymalizacji jest dodanie instrukcji warunkowej, która sprawdza, czy nastąpiła zamiana elementów po pierwszym przejściu pętli, jeżeli nie – lista jest posortowana.

Różnice w stosunku do sortowania bąbelkowego

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 jedna 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ść.

Złożoność

Typowa czasowa złożoność obliczeniowa sortowania koktajlowego jest klasy $O(n^2)$, jednak przy sortowaniu zbiorów w znacznym stopniu posortowanych klasa złożoności obliczeniowej redukuje się do $O(n)$