Sortowanie bąbelkowe a przez scalanie: różnice i złożoność
Bąbelkowe porównuje sąsiednie elementy i zamienia je miejscami, w pesymistycznym przypadku kwadratowo; przez scalanie dzieli tablicę na pół, sortuje połowy i je scala, zawsze w czasie n log n.
Różnica między tymi dwoma algorytmami nie jest różnicą szybkości implementacji — jest różnicą pomysłu. Sortowanie bąbelkowe poprawia tablicę lokalnie: przechodzi po niej wielokrotnie i za każdym razem zamienia miejscami sąsiadów stojących w złej kolejności. Sortowanie przez scalanie robi coś przeciwnego: nie poprawia niczego lokalnie, tylko rozbija problem na dwa mniejsze, rozwiązuje je tym samym sposobem i dopiero łączy wyniki.
Z tego bierze się złożoność. Bąbelkowe w najgorszym przypadku musi wykonać przebieg dla każdego elementu, a w każdym przebiegu porównać niemal wszystkie pary sąsiadów — liczba operacji rośnie więc z kwadratem liczby elementów. Przez scalanie dzieli tablicę na pół tyle razy, ile razy da się ją podzielić, czyli logarytmicznie względem jej długości, a na każdym poziomie podziału wykonuje pracę proporcjonalną do liczby elementów. Stąd iloczyn: liczba elementów razy logarytm z niej.
Cena za tę szybkość jest pamięciowa. Scalanie dwóch posortowanych fragmentów wymaga miejsca, w którym powstaje wynik, więc klasyczna wersja algorytmu potrzebuje dodatkowej tablicy wielkości danych wejściowych. Bąbelkowe pracuje w miejscu i nie potrzebuje praktycznie żadnej dodatkowej pamięci. Na maturze to rozróżnienie wraca w zadaniach o zasobach, nie tylko o czasie.
Jest też cecha, o którą zadania pytają wprost i która bywa zaskoczeniem: oba algorytmy są stabilne, to znaczy nie zmieniają wzajemnej kolejności elementów o równych kluczach — pod warunkiem że scalanie przy remisie bierze element z lewego fragmentu. Stabilność ma znaczenie, gdy dane sortuje się kolejno po kilku polach.
Sortowanie bąbelkowe a przez scalanie: porównanie w tabeli
| Kryterium | Sortowanie bąbelkowe | Sortowanie przez scalanie |
|---|---|---|
| Zasada | wielokrotne przejścia z zamianą sąsiadów | podział na pół, sortowanie połówek, scalanie |
| Złożoność czasowa — przypadek pesymistyczny | proporcjonalna do kwadratu liczby elementów | proporcjonalna do n log n |
| Złożoność czasowa — dane już posortowane | liniowa, jeśli algorytm przerywa po przebiegu bez zamiany | nadal n log n — podział zachodzi niezależnie od danych |
| Pamięć dodatkowa | stała — sortuje w miejscu | proporcjonalna do liczby elementów |
| Rodzaj algorytmu | iteracyjny | rekurencyjny, w schemacie dziel i zwyciężaj |
| Stabilność | stabilne | stabilne, gdy przy remisie wybiera element z lewej części |
| Kiedy ma sens | bardzo małe zbiory, dane niemal posortowane, nauka mechanizmu | duże zbiory, gdy gwarancja czasu jest ważniejsza niż pamięć |
Gdzie najczęściej ginie punkt
- Podanie samej nazwy złożoności bez uzasadnienia, gdy polecenie pytało, z czego ona wynika. Punkt jest za wskazanie liczby przebiegów i liczby porównań w przebiegu, nie za sam zapis.
- Twierdzenie, że sortowanie przez scalanie jest szybsze zawsze. Dla kilku elementów narzut podziału i scalania bywa większy niż cały koszt bąbelkowego.
- Pominięcie pamięci dodatkowej przy porównaniu algorytmów, gdy polecenie pytało o zasoby, a nie wyłącznie o czas.
- Opis bąbelkowego jako „szukania najmniejszego elementu i przesuwania go na początek”. To jest sortowanie przez wybór — inny algorytm, inna liczba zamian.