Sortowanie koktajlowe - Cocktail Sort

Sortowanie koktajlowe, czyli Cocktail Sort, jest rozwinięciem dobrze znanego sortowania bąbelkowego. Różnica jest łatwa do zauważenia: zamiast przechodzić przez tablicę tylko w jednym kierunku, algorytm porusza się raz od lewej do prawej, a potem wraca od prawej do lewej. Dzięki temu duże wartości szybko przesuwają się na koniec, a małe nie muszą czekać wielu kolejnych przebiegów, żeby dotrzeć w stronę początku tablicy. Sam pomysł jest prosty, a kod pozostaje stosunkowo łatwy do prześledzenia, dlatego Cocktail Sort dobrze nadaje się do nauki podstaw sortowania.

Sortowanie koktajlowe - na czym polega?

Jeśli znasz już sortowanie bąbelkowe, Cocktail Sort będzie bardzo łatwy do zrozumienia. Oba algorytmy porównują elementy stojące obok siebie i zamieniają je miejscami, jeśli znajdują się w złej kolejności.

W zwykłym sortowaniu bąbelkowym idziemy jednak przez tablicę od początku do końca. Po takim przejściu największa wartość trafia na prawą stronę. Potem znów zaczynamy od lewej.

Sortowanie koktajlowe robi coś jeszcze. Po przejściu w prawo nie wraca od razu na początek. Zmienia kierunek i zaczyna przechodzić przez tablicę od końca do początku.

W efekcie podczas jednego pełnego cyklu dzieją się dwie rzeczy:

  • duże wartości przesuwają się w prawo,
  • małe wartości przesuwają się w lewo.

I właśnie to odróżnia Cocktail Sort od prostszego sortowania bąbelkowego.

Dlaczego algorytm przechodzi w dwie strony?

Najlepiej zobaczyć sens tej zmiany na przykładzie tablicy, w której bardzo mała liczba znalazła się blisko końca:

[2, 3, 4, 5, 6, 1]

W sortowaniu bąbelkowym liczba 1 może przesuwać się w stronę początku tylko wtedy, gdy kolejne przebiegi ponownie zaczynają się od lewej strony. Jej droga jest więc dość powolna.

Cocktail Sort po pierwszym przejściu od lewej do prawej od razu zawraca. Podczas ruchu w lewo porównuje kolejne pary i przesuwa małą wartość w stronę początku.

Można więc powiedzieć, że zwykłe sortowanie bąbelkowe jest szczególnie dobre w wypychaniu dużych elementów na koniec. Sortowanie koktajlowe robi to samo, ale przy okazji sprawniej przenosi małe wartości na początek.

Cocktail Sort na prostym przykładzie

Weźmy tablicę:

[5, 1, 4, 2, 8]

Pierwszy przebieg wykonujemy od lewej do prawej.

Porównujemy 5 i 1. Są w złej kolejności, więc zamieniamy je:

[1, 5, 4, 2, 8]

Teraz 5 i 4:

[1, 4, 5, 2, 8]

Następnie 5 i 2:

[1, 4, 2, 5, 8]

Ostatnia para to 5 i 8. Tutaj niczego nie zmieniamy:

[1, 4, 2, 5, 8]

Największa wartość, czyli 8, znajduje się już na końcu. Teraz zmieniamy kierunek.

Idąc od prawej strony, porównujemy 2 i 5 - wszystko jest w porządku. Następnie trafiamy na:

4 i 2

Zamieniamy je:

[1, 2, 4, 5, 8]

Tablica po jednym cyklu jest już bardzo blisko pełnego uporządkowania. Kolejny przebieg nie wykona żadnej zamiany, więc algorytm może zakończyć pracę.

Dlaczego zakres sortowania się zmniejsza?

Po przejściu od lewej do prawej największy element trafia na prawidłową pozycję na końcu tablicy. Nie ma powodu sprawdzać go ponownie.

Po przejściu w przeciwną stronę podobnie dzieje się z najmniejszym elementem - trafia na właściwe miejsce z lewej strony.

Dlatego po każdym pełnym cyklu możemy zmniejszyć analizowany fragment tablicy z obu stron.

Można to zobrazować tak:

[  nieposortowany fragment  ]

[1 |  nieposortowany fragment  | 8]

[1, 2 | nieposortowane | 7, 8]

Granice stopniowo zbliżają się więc do środka. To drobna optymalizacja, ale pozwala uniknąć sprawdzania elementów, których pozycja jest już ustalona.

Sortowanie koktajlowe w Pythonie

Implementacja w Pythonie jest trochę dłuższa niż przy klasycznym sortowaniu bąbelkowym, bo musimy obsłużyć dwa kierunki i dwie granice sortowanego obszaru.

def cocktail_sort(tablica):
    start = 0
    koniec = len(tablica) - 1
    zamiana = True

    while zamiana:
        zamiana = False

        for i in range(start, koniec):
            if tablica[i] > tablica[i + 1]:
                tablica[i], tablica[i + 1] = tablica[i + 1], tablica[i]
                zamiana = True

        if not zamiana:
            break

        zamiana = False
        koniec -= 1

        for i in range(koniec - 1, start - 1, -1):
            if tablica[i] > tablica[i + 1]:
                tablica[i], tablica[i + 1] = tablica[i + 1], tablica[i]
                zamiana = True

        start += 1


tablica = [5, 1, 4, 2, 8]

print("Przed sortowaniem:", tablica)

cocktail_sort(tablica)

print("Po sortowaniu:", tablica)

Po uruchomieniu otrzymamy:

Przed sortowaniem: [5, 1, 4, 2, 8]
Po sortowaniu: [1, 2, 4, 5, 8]

Jak działa kod Cocktail Sort?

Na początku ustawiamy granice obszaru, którym zajmuje się algorytm:

start = 0
koniec = len(tablica) - 1

Pierwszy przebieg idzie od lewej strony w prawo:

for i in range(start, koniec):

Porównujemy dwa sąsiadujące elementy:

if tablica[i] > tablica[i + 1]:

Jeżeli są ustawione odwrotnie, wykonujemy zamianę:

tablica[i], tablica[i + 1] = tablica[i + 1], tablica[i]

Po takim przebiegu największy element analizowanego fragmentu znajduje się na końcu. Możemy więc zmniejszyć prawą granicę:

koniec -= 1

Teraz przechodzimy w przeciwnym kierunku:

for i in range(koniec - 1, start - 1, -1):

Porównania są dokładnie takie same jak wcześniej, ale indeks przesuwa się od prawej do lewej.

Po tym przebiegu najmniejszy element analizowanego fragmentu powinien znaleźć się z lewej strony, dlatego przesuwamy również początek:

start += 1

W następnym cyklu algorytm pracuje już na mniejszym fragmencie tablicy.

Sortowanie koktajlowe a sortowanie bąbelkowe

Cocktail Sort jest bardzo blisko spokrewniony z sortowaniem bąbelkowym. W obu przypadkach podstawową operacją pozostaje porównanie dwóch sąsiadów i ewentualna zamiana ich miejscami.

Cecha Sortowanie koktajlowe Sortowanie bąbelkowe
Kierunek przejścia W prawo i w lewo Głównie w jednym kierunku
Przesuwanie dużych wartości Szybko w stronę końca Szybko w stronę końca
Przesuwanie małych wartości Sprawnie podczas przejścia w lewo Może wymagać wielu przebiegów
Najgorszy przypadek O(n²) O(n²)
Dodatkowa pamięć O(1) O(1)

Największą różnicę widać więc wtedy, gdy w tablicy znajduje się mały element mocno przesunięty w prawo. Sortowanie koktajlowe może szybko przenieść go w lewo podczas przebiegu powrotnego.

Nie zmienia to faktu, że oba algorytmy należą do prostych metod opartych na sąsiednich zamianach i przy większej liczbie elementów istnieją dużo sprawniejsze sposoby sortowania.

Złożoność sortowania koktajlowego

W najgorszym przypadku Cocktail Sort ma złożoność O(n²). Pod tym względem nie rozwiązuje podstawowego problemu sortowania bąbelkowego.

Dla dobrze ułożonych lub prawie posortowanych danych sytuacja może wyglądać znacznie lepiej. Jeżeli podczas pierwszego przejścia nie dojdzie do żadnej zamiany, algorytm może zakończyć pracę bez wykonywania wszystkich możliwych przebiegów.

Przypadek Złożoność
Najlepszy O(n)
Przeciętny O(n²)
Najgorszy O(n²)
Dodatkowa pamięć O(1)

Algorytm wykonuje zamiany bezpośrednio wewnątrz tablicy, więc nie potrzebuje drugiej struktury o podobnym rozmiarze.

Sortowanie koktajlowe może być stabilne przy klasycznej implementacji, w której zamieniamy elementy wyłącznie wtedy, gdy pierwszy jest rzeczywiście większy od drugiego. Elementów równych nie trzeba wtedy przestawiać.

Kiedy algorytm może zakończyć pracę wcześniej?

Zmiennej zamiana nie dodajemy tylko dla wygody. Pozwala ona uniknąć dalszych przebiegów, gdy tablica jest już uporządkowana.

Po przejściu od lewej do prawej sprawdzamy:

if not zamiana:
    break

Jeśli nie wykonaliśmy ani jednej zamiany, wszystkie sąsiadujące elementy znajdują się we właściwej kolejności. Tablica jest więc posortowana i nie ma potrzeby wykonywać przejścia powrotnego.

To szczególnie przydatne przy danych, które już na początku są całkowicie albo prawie uporządkowane.

Cocktail Sort jest więc ciekawym przykładem tego, jak można zmodyfikować prosty algorytm bez całkowitej zmiany jego sposobu działania. Nadal wykonujemy te same lokalne porównania co w sortowaniu bąbelkowym, ale zmiana kierunku pozwala trochę sprawniej radzić sobie z elementami znajdującymi się po niewłaściwej stronie tablicy.

FAQ - sortowanie koktajlowe

Co to jest sortowanie koktajlowe?
Sortowanie koktajlowe to odmiana sortowania bąbelkowego, w której tablica jest przeglądana w dwóch kierunkach. Najpierw algorytm idzie od lewej do prawej, a później wraca od prawej do lewej.
Jak działa Cocktail Sort krok po kroku?
Algorytm porównuje sąsiadujące elementy i zamienia je, gdy są ustawione w złej kolejności. Po przejściu w prawo największa wartość trafia bliżej końca, a podczas powrotu w lewo małe wartości szybciej przesuwają się na początek.
Czym sortowanie koktajlowe różni się od bąbelkowego?
Sortowanie bąbelkowe przechodzi przez tablicę głównie w jednym kierunku. Cocktail Sort wykonuje dodatkowo przebieg powrotny, dzięki czemu małe liczby znajdujące się pod koniec tablicy nie muszą przesuwać się tylko podczas kolejnych pełnych przebiegów.
Jaka jest złożoność sortowania koktajlowego?
W przeciętnym i najgorszym przypadku złożoność wynosi O(n²). Dla tablicy już posortowanej algorytm z kontrolą wykonanych zamian może zakończyć pracę po jednym przebiegu, czyli w czasie O(n).
Jak napisać Cocktail Sort w Pythonie?
Najprostsza implementacja wykorzystuje dwie pętle: jedną przechodzącą od początku do końca aktualnego zakresu i drugą działającą w przeciwnym kierunku. Potrzebna jest też zmienna informująca, czy podczas przebiegu wykonano zamianę.
Czy sortowanie koktajlowe jest stabilne?
Tak, klasyczna wersja może zachować stabilność, jeśli dwa elementy są zamieniane tylko wtedy, gdy pierwszy jest większy od drugiego. Równych wartości nie trzeba wtedy przestawiać względem siebie.
Kiedy Cocktail Sort kończy sortowanie?
Algorytm może zakończyć pracę wtedy, gdy podczas całego przebiegu nie zostanie wykonana żadna zamiana. Oznacza to, że wszystkie sąsiadujące elementy znajdują się już w odpowiedniej kolejności.
Czy Cocktail Sort jest szybszy od sortowania bąbelkowego?
W niektórych układach danych może poradzić sobie lepiej, zwłaszcza gdy małe wartości znajdują się daleko po prawej stronie tablicy. Nadal jednak oba algorytmy mają złożoność O(n²) w najgorszym przypadku, więc przy dużych zbiorach istnieją wydajniejsze rozwiązania.

Komentarze