Comb Sort - sortowanie grzebieniowe

Comb Sort, czyli sortowanie grzebieniowe, wyrósł z bardzo prostego pomysłu: skoro sortowanie bąbelkowe radzi sobie gorzej z elementami znajdującymi się daleko od właściwej pozycji, można zacząć od porównywania liczb oddalonych od siebie o kilka miejsc. Dopiero później ten odstęp jest stopniowo zmniejszany. Na końcu algorytm rzeczywiście zaczyna przypominać klasyczne sortowanie bąbelkowe, ale wtedy tablica jest już częściowo uporządkowana. Dzięki temu wiele elementów trafia w okolice właściwych pozycji znacznie wcześniej.

Skąd wziął się pomysł na Comb Sort?

Żeby zrozumieć Comb Sort, najlepiej najpierw przypomnieć sobie, jak działa sortowanie bąbelkowe. Tam porównujemy element z jego bezpośrednim sąsiadem. Jeśli stoją w złej kolejności, zamieniamy je miejscami i przechodzimy dalej.

Taki sposób jest prosty, ale ma jedną irytującą cechę. Element, który znajduje się bardzo daleko od miejsca, w którym ostatecznie powinien się znaleźć, przesuwa się powoli. Szczególnie dobrze widać to na małych liczbach znajdujących się pod koniec tablicy.

Weźmy taki zestaw:

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

Liczba 1 powinna znaleźć się na samym początku, ale w sortowaniu bąbelkowym nie przeskoczy od razu o kilka pozycji. Musi przesuwać się krok po kroku przez kolejne zamiany.

Comb Sort próbuje ominąć właśnie ten problem. Na początku pozwala porównywać elementy, które znajdują się daleko od siebie. Dzięki temu jedna zamiana może przesunąć liczbę o kilka miejsc, a nie tylko o jedno.

Stąd też określenie "sortowanie grzebieniowe". Można sobie wyobrazić grzebień o szeroko rozstawionych zębach, który z każdym kolejnym przejściem staje się coraz gęstszy.

Jak działa sortowanie grzebieniowe?

W sortowaniu bąbelkowym odległość pomiędzy porównywanymi elementami zawsze wynosi 1. Porównujemy więc:

tablica[0] z tablica[1]
tablica[1] z tablica[2]
tablica[2] z tablica[3]

Comb Sort wprowadza dodatkową wartość, nazywaną zazwyczaj gap. Określa ona odstęp pomiędzy dwoma elementami, które aktualnie ze sobą porównujemy.

Jeśli gap wynosi 5, pierwsze porównania mogą wyglądać tak:

tablica[0] z tablica[5]
tablica[1] z tablica[6]
tablica[2] z tablica[7]

Przy odstępie równym 3:

tablica[0] z tablica[3]
tablica[1] z tablica[4]
tablica[2] z tablica[5]

Za każdym przejściem odstęp maleje. W końcu dochodzi do 1. Wtedy Comb Sort przechodzi w etap bardzo podobny do sortowania bąbelkowego, ponieważ zaczyna porównywać sąsiadujące ze sobą elementy.

Różnica jest taka, że wcześniej zdążyliśmy już poprzesuwać najbardziej problematyczne wartości. Końcowe przejścia mają więc znacznie mniej pracy.

Odstęp między elementami - najważniejszy pomysł Comb Sort

Odstępu nie zmniejsza się zwykle o jeden. Gdyby tablica miała kilkaset czy kilka tysięcy elementów, taki sposób oznaczałby ogromną liczbę niepotrzebnych przejść.

W klasycznej wersji Comb Sort stosuje się współczynnik zmniejszania wynoszący około 1,3. Oznacza to, że po każdym przejściu aktualny odstęp dzielimy przez 1,3.

Dla tablicy zawierającej 20 elementów kolejne odstępy mogą wyglądać mniej więcej tak:

Nie trzeba zapamiętywać tych konkretnych wartości. Istotny jest sam kierunek działania: najpierw duże skoki, później coraz dokładniejsze porządkowanie tablicy.

Kiedy po podzieleniu odstępu otrzymalibyśmy wartość mniejszą od 1, ustawiamy po prostu gap = 1. Od tej chwili algorytm porównuje już sąsiadujące elementy.

Comb Sort na konkretnym przykładzie

Spójrzmy na tablicę:

[9, 4, 7, 3, 8, 2, 6, 1]

Znajduje się w niej 8 elementów. Po pierwszym zmniejszeniu odstępu otrzymamy w przybliżeniu:

8 / 1.3 ≈ 6

Porównujemy więc pierwszy element z elementem oddalonym o sześć pozycji:

9 i 6

Są ustawione nieprawidłowo, więc wykonujemy zamianę:

[6, 4, 7, 3, 8, 2, 9, 1]

Następnie porównujemy:

4 i 1

Po kolejnej zamianie mamy:

[6, 1, 7, 3, 8, 2, 9, 4]

To właśnie tutaj dobrze widać sens Comb Sort. Liczba 1 znajdowała się na ostatniej pozycji, a po jednej zamianie trafiła prawie na początek tablicy. W zwykłym sortowaniu bąbelkowym potrzebowałaby do tego kilku kolejnych porównań i zamian.

W kolejnym przejściu odstęp jest mniejszy:

6 / 1.3 ≈ 4

Teraz algorytm wykonuje porównania co cztery miejsca. Później odstęp zmniejszy się do 3, następnie 2 i na końcu 1.

Gdy odstęp wynosi już 1, mechanizm jest praktycznie taki sam jak przy sortowaniu bąbelkowym. Nadal trzeba jednak wykonywać kolejne przebiegi do momentu, aż cały zostanie zakończony bez żadnej zamiany.

Po zakończeniu pracy otrzymujemy:

[1, 2, 3, 4, 6, 7, 8, 9]

Comb Sort w Pythonie

Kod nie jest szczególnie długi. W porównaniu z najprostszą implementacją sortowania bąbelkowego dochodzą właściwie dwa elementy: zmienny odstęp oraz informacja o tym, czy podczas ostatniego przejścia wykonaliśmy jakąkolwiek zamianę.

def comb_sort(tablica):
    gap = len(tablica)
    shrink = 1.3
    zamiana = True

    while gap > 1 or zamiana:
        gap = int(gap / shrink)

        if gap < 1:
            gap = 1

        zamiana = False
        i = 0

        while i + gap < len(tablica):
            if tablica[i] > tablica[i + gap]:
                tablica[i], tablica[i + gap] = tablica[i + gap], tablica[i]
                zamiana = True

            i += 1


tablica = [9, 4, 7, 3, 8, 2, 6, 1]

print("Przed sortowaniem:", tablica)

comb_sort(tablica)

print("Po sortowaniu:", tablica)

Wynik:

Przed sortowaniem: [9, 4, 7, 3, 8, 2, 6, 1]
Po sortowaniu: [1, 2, 3, 4, 6, 7, 8, 9]

Co właściwie dzieje się w kodzie?

Na początku odstęp jest równy długości tablicy:

gap = len(tablica)

Nie oznacza to jeszcze, że będziemy porównywać pierwszy element z elementem znajdującym się poza tablicą. Przed rozpoczęciem pierwszych porównań wartość zostaje zmniejszona:

gap = int(gap / shrink)

Współczynnik przechowujemy osobno:

shrink = 1.3

Po każdym pełnym przejściu przez tablicę gap maleje. Gdy zrobi się zbyt mały, ustawiamy go na 1:

if gap < 1:
    gap = 1

W środku porównujemy element znajdujący się pod indeksem i z elementem oddalonym właśnie o aktualny odstęp:

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

Jeżeli wartości stoją w złej kolejności, następuje zamiana:

tablica[i], tablica[i + gap] = tablica[i + gap], tablica[i]

Przy okazji zapisujemy informację, że coś się zmieniło:

zamiana = True

To potrzebne szczególnie pod koniec. Kiedy gap osiągnie 1, samo dojście do końca tablicy nie oznacza jeszcze, że wszystko jest posortowane. Tak samo jak w sortowaniu bąbelkowym może być potrzebne kolejne przejście.

Dlatego główna pętla ma warunek:

while gap > 1 or zamiana:

Kończymy dopiero wtedy, gdy odstęp wynosi 1 i podczas ostatniego przebiegu nie doszło do żadnej zamiany.

Comb Sort a sortowanie bąbelkowe

Podobieństwo między tymi algorytmami nie jest przypadkowe. Comb Sort został pomyślany jako sposób na ograniczenie jednego z największych problemów, jakie ma sortowanie bąbelkowe: bardzo powolnego przesuwania elementów znajdujących się daleko od swojej docelowej pozycji.

Największa różnica jest więc bardzo prosta. Sortowanie bąbelkowe od początku "patrzy" tylko na sąsiadów. Comb Sort najpierw patrzy dużo dalej, a dopiero na końcu zajmuje się drobnymi poprawkami.

Nie oznacza to jednak, że sortowanie grzebieniowe całkowicie odcina się od swojego prostszego odpowiednika. Gdy gap dochodzi do 1, końcówka działania Comb Sort wygląda bardzo podobnie do sortowania bąbelkowego.

Złożoność Comb Sort

Comb Sort potrafi zachowywać się sprawniej od klasycznego sortowania bąbelkowego, ale nadal nie jest algorytmem z gwarantowaną złożonością O(n log n).

W najgorszym przypadku złożoność czasowa wynosi O(n²). Przy większych zbiorach danych istnieją więc algorytmy o znacznie lepszych właściwościach.

Nie zmienia to faktu, że sam pomysł jest ciekawy. Wprowadzenie dużego odstępu pozwala stosunkowo tanio rozwiązać problem wolnego przemieszczania wartości, który dobrze znamy z sortowania bąbelkowego.

Algorytm pracuje bezpośrednio na przekazanej tablicy, dlatego nie potrzebuje dodatkowej tablicy o podobnym rozmiarze. Dodatkowe zapotrzebowanie na pamięć wynosi więc O(1).

Comb Sort nie jest natomiast algorytmem stabilnym. Zamiana dwóch oddalonych od siebie elementów może zmienić kolejność danych mających tę samą wartość.

Typowe błędy przy implementacji

Pierwszy błąd jest dość naturalny: ktoś widzi, że odstęp stopniowo spada do 1, więc zakłada, że właśnie wtedy należy zakończyć sortowanie. Nie zawsze.

Przy gap = 1 tablica może nadal wymagać kilku zamian. Trzeba więc kontynuować pracę tak długo, aż cały przebieg zostanie wykonany bez żadnej zmiany.

Drugi problem pojawia się przy obliczaniu odstępu:

gap = int(gap / 1.3)

Po pewnym czasie taki zapis może dać 0. Tymczasem odstęp równy zero nie ma tutaj sensu. Z tego powodu minimalną wartością pozostaje 1.

Trzeba też uważać na indeks:

tablica[i + gap]

Pętla nie może dopuścić do sytuacji, w której i + gap wyjdzie poza koniec tablicy. Stąd warunek:

while i + gap < len(tablica):

Gdy zrozumiemy te trzy rzeczy - malejący odstęp, sprawdzanie wykonanych zamian i pilnowanie indeksów - reszta Comb Sort jest już dość łatwa do prześledzenia.

FAQ - Comb Sort