Sortowanie koktajlowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Sortowanie koktajlowe
Sorting shaker sort anim.gif
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[edytuj]

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[edytuj]

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[edytuj]

  • 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[edytuj]

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ść[edytuj]

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)