Sortowanie koktajlowe
Z Wikipedii
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.
Spis treści |
[edytuj] 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.
[edytuj] Kod źródłowy
Przykład implementacji algorytmu w języku C:
function cocktail_sort(list, list_length) // pierwszy element zbioru ma index 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; } }
[edytuj] 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.
[edytuj] 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ść.
[edytuj] Złożoność
Typowa czasowa złożoność obliczeniowa sortowania koktajlowego jest klasy O(n2), jednak przy sortowaniu zbiorów w znacznym stopniu posortowanych klasa złożoności obliczeniowej redukuje się do O(n)
