Sortowanie w czasie liniowym

Teoria mówi, że optymalna złożoność obliczeniowa dla algorytmów sortowania opartych o porównywanie wynosi O(nlogn), czyli, innymi słowy, szybciej być już nie może. Taką złożoność optymistyczną ma na przykład używany w .NET algorytm sortowania szybkiego. Ale chwila, co to znaczy sortowanie oparte o porównywanie? To w ogóle istnieje inna możliwość? Przecież, aby posortować na przykład listę liczb całkowitych, to trzeba je porównywać!

Okazuje się, że do problemu można podejść inaczej. Jeśli zrezygnujemy z porównywania, to, pod pewnymi warunkami, osiągniemy złożoność liniową O(n). Niby szybciej, ale czy rzeczywiście warto się tym przejmować? Postanowiłem to sprawdzić i porównałem zachowanie algorytmu sortowania używanego przez .NET, naiwnej rekurencyjnej implementacji sortowania szybkiego oraz algorytmu sortowania w czasie liniowym o nazwie sortowanie przez zliczanie.

Sortowanie przez zliczanie zostało opisane choćby na Wikipedii, dlatego tutaj przybliżę tylko jego ideę. Zacznijmy od tego, że algorytm ten bardzo dobrze nadaje się do sortowania liczb całkowitych z zadanego zakresu, powiedzmy od K do N. Im N mniejsze tym lepiej i jest to oczywiście istotne jego ograniczenie. Jego działanie opiera się na policzeniu, ile razy w tablicy do posortowania pojawiła się liczba K, ile razy liczba K + 1 ... i ile razy liczba N. W tym celu wystarczy odwiedzić każdy element tablicy tylko raz. Kiedy mamy już te informacje, sortowanie właściwie jest zakończone. Na przykład: jeśli liczba 0 wystąpiła 10 razy, a liczba 3 wystąpiła 2 itd., to jako wynik wypiszemy najpierw 10 razy 0, potem 2 razy 3 itd.

Wyniki porównania wspomnianych 3 algorytmów zaprezentowałem na 2 wykresach poniżej. Oś X pokazuje liczbę elementów do posortowania, a oś Y czas sortowania w ms. Pierwszy wykres pokazuje przypadek, kiedy dane do posortowania zawierały liczby z zakresu od 0 do 100, a drugi od 0 do 100 tysięcy.



Wnioski są następujące, niektóre bardzo ciekawe:

• Dla małego zakresu liczb naiwna implementacja sortowania szybkiego działa bardzo słabo (mamy tutaj pesymistyczny przypadek i złożoność O(n^2)).
• Nie widać tego na wykresie, lecz dla małego zakresu liczb sortowanie przez zliczanie jest nieznacznie szybsze od implementacji używanej przez .NET: dla 1 miliona elementów jest to 15 ms w porównaniu do 64 ms.
• W związku z tym pojawia się pytanie, czym różni się naiwna rekurencyjna implementacja sortowania szybkiego od tej używanej przez .NET? Można by o tym dużo napisać, więc tutaj tylko zasygnalizuję o co chodzi. Otóż w rzeczywistości .NET używa tzw. sortowanie introspektywnego, który stanowi połączenie "zwykłego" sortowania szybkiego, sortowania przez kopcowanie i sortowania przez wstawianie, przez co wyeliminowano przypadek pesymistyczny, kiedy QuickSort ma złożoność wielomianową.
• Dla dużego zakresu elementów różnica pomiędzy 3 porównywanymi algorytmami zaciera się chociaż rekurencyjna implementacja QuickSort jest wciąż najwolniejsza, a sortowanie przez zliczanie jest trochę szybsze od tego co oferuje .NET.
• Sprawdziłem czas sortowania dla maksymalnie 50 milionów elementów i trwało to 2 s dla sortowanie przez zliczanie oraz 5 s dla hybrydowego.
• Wniosek końcowy jest taki, że biorąc pod uwagę ograniczenia i wady sortowania przez zliczanie oraz to, jak dobrze działa implementacja hybrydowa w .NET należy jej po prostu używać i nie zastanawiać się specjalnie nad innymi wynalazkami.