Sortowanie koktajlowe

Sortowanie koktajlowe

Przykład działania sortowania koktajlowego
Rodzaj	Sortowanie
Struktura danych	Tablica, lista
Złożoność
Czasowa	$O(n^{2})$
Pamięciowa	$O(1)$

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.

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 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;
    }
}

Optymalizacja

• Jednym ze sposobów 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.

• Progi oznaczone wyżej jako bottom i top można także odpowiednio zwiększać i zmniejszać o wartość większą niż 1 – w zależności od tego, na którym indeksie nastąpiła ostatnia zamiana w danym obiegu. Następne elementy muszą być posortowane i możemy już ich nie brać pod uwagę.

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

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)$