Sortowanie koktajlowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

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

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

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

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

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)