Kwadratowe metody sortowania

Sortowanie bąbelkowe

Wstęp

Sortowanie bąbelkowe jest prostą metodą porządkowania zbioru. Prostota tego algorytmu jest prawdopodobnie jedną z jego dwóch zalet (drugą zaletą jest to, że działa). Do wad należy złożoność obliczeniowa (kwadratowa), a także fakt, że ilość wykonanych operacji jest niezależna od permutacji elementów (dotyczy podstawowej wersji algorytmu), bowiem zawsze, niezależnie od ułożenia elementów zbioru, musimy wykonać tą samą liczbę porównań.

Wersja podstawowa

Algorytm sortowania bąbelkowego w podstawowej wersji polega na cyklicznym porównywaniu między sobą kolejnych par elementów leżących obok siebie i zamianie ich miejscami, jeśli nie stoją w porządku jaki chcemy uzyskać w posortowanej tablicy.

Przykładowo jeśli chcemy posortować ciąg n-elementów rosnąco - wygląda to tak, że element, który był większy w pierwszej parze jest tak długo przesuwany w ciągu, aż napotkany zostanie element większy od niego, wtedy w następnych krokach przesuwany jest ten większy. Po pierwszym takim przebiegu ciąg nie musi być jeszcze uporządkowany, ale na pozycji ostatniej z pewnością znajdzie się największa wartość.

Zatem w kolejnym przebiegu można porządkować ciąg o jeden krótszy, czyli tylko elementy od pierwszego do przedostatniego. Po drugim przebiegu, dwa ostatnie elementy są na swoich miejscach, czyli pozostaje posortować ciąg o dwa elementy krótszy, itd.

Złożoność algorytmu dla ciągu n-elementowego w takiej wersji wynosi:

(n−1)+(n−2)+(n−3)+…+1=n∗(n−1)2

więc jest klasy O(n²).

Modyfikacje pozwalające na niewielką poprawę efektywności

Nie da się zmniejszyć ilości operacji zamian elementów, jednakże możliwa jest pewna redukcja ilości operacji „jałowych” porównań (porównania mogą dotyczyć elementów, których wcale nie trzeba przestawiać).

Sprytniejsze ustawienie kresu górnego.

Sposób ten opiera się na obserwacji, że jeżeli w pewnym przebiegu ostatnia zamiana dotyczyła elementów o indeksie i orazi+1, to w następnym przebiegu wystarczy porządkować tylko elementy na pozycjach do i-1.

Wystarczy wprowadzić zmienną, która zapamięta na której pozycji nastąpiła ostatnia zamiana elementów tablicy. Ta zmienna ustanowi kres następnego przebiegu. Może to dać pewne usprawnienie działania algorytmu w porównaniu z wersją, w której przesuwamy kres po każdym przebiegu na sztywno tylko o jeden.

Dodatkowo, jeśli podczas danego przebiegu nie miały miejsca przestawienia elementów, to zbiór jest już posortowany i możemy zakończyć pracę algorytmu bez kolejnego przebiegu.

Należy jednak pamiętać, że przy najbardziej pechowym układzie elementów algorytm będzie po staremu przestawiał na każdej albo prawie każdej pozycji, zatem mimo ulepszeń będzie posiadał klasę złożoności taką jak w wersji podstawowej O(n²).

Sortowanie bąbelkowe dwukierunkowe (cocktail sort)

Dwukierunkowe sortowanie bąbelkowe oparte jest na spostrzeżeniu, że po każdym przebiegu wewnętrznej pętli sortującej na właściwym miejscu ląduje element największy, a elementy mniejsze przesuwają się zwykle o 1 pozycję w kierunku początku. Jeśli teraz wykonać przebieg w kierunku odwrotnym, to najmniejszy element znajdzie się na swoim właściwym miejscu, a elementy większe przesuną się w kierunku końca zbioru. Połączmy te dwie pętle sortując wewnętrznie naprzemiennie w kierunku normalnym i odwrotnym, a otrzymamy algorytm dwukierunkowego sortowania bąbelkowego.

Wykonanie pętli sortującej w normalnym kierunku ustali maksymalną pozycję w zbiorze, od której powinna rozpocząć sortowanie pętla odwrotna. Ta z kolei ustali minimalną pozycję w zbiorze, od której powinna rozpocząć sortowanie pętla normalna w następnym obiegu pętli zewnętrznej. Sortowanie możemy zakończyć, jeśli nie wystąpiła potrzeba zamiany elementów w żadnej z tych dwóch pętli.

Implementacja