Sortowanie koktajlowe
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.
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 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
[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 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ść
[edytuj | edytuj kod]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