Sortowanie szybkie
Wybiera jedną wartość, zwaną pivotem, i przenosi mniejsze wartości na lewo od niej, a większe na prawo. Potem robi to samo z każdą stroną.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- nie
- tak
Najlepszy przypadek: jak czas rośnie z rozmiarem listy n, gdy dane są dla tego algorytmu najłatwiejsze.
Średni: jak czas zwykle rośnie z n. Przy n² dwa razy więcej wartości sortuje się około czterech razy dłużej; n log n rośnie dużo wolniej.
Najgorszy przypadek: jak rośnie czas przy najtrudniejszych danych. Ważny, gdy sortowanie nigdy nie może zwolnić.
Pamięć: ile dodatkowej pamięci potrzeba poza listą. 1 to kilka zmiennych, n to kopia listy.
Stabilny: dwie równe wartości zachowują pierwotną kolejność. Ważne przy sortowaniu rekordów według jednego pola.
Bez dodatkowej pamięci: sortuje w samej liście, bez drugiej listy.
- porównywanie
- przenoszenie
- pivot
- na właściwym miejscu
Spróbuj: Wybierz listę odwróconą. Pivot jest zawsze najmniejszy albo największy z pozostałych, więc jedna strona jest pusta, a koszt rośnie do n².
Jak to działa
Pivotem jest tu ostatnia wartość w zakresie. Idąc od lewej do prawej, algorytm przerzuca na lewą stronę każdą wartość nie większą od pivota. Potem pivot staje między obiema stronami i już się nie ruszy. Każdą stronę sortuje się tak samo.
Kiedy warto go użyć
W praktyce jeden z najszybszych sposobów sortowania, do tego prawie bez dodatkowej pamięci. Gdy jednak raz po raz trafia na zły pivot, na przykład na już posortowanej liście, zwalnia. Dlatego w bibliotekach pivot wybiera się staranniej.