Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

Sortowanie szybkie jest dość podobne do sortowania scalającego w tym sensie, że algorytm ten pomaga programistom dzielić i zdobywać. Wybiera on elementy jako punkt obrotu, po czym tworzy partycje w tablicy. Szybkie sortowanie ma wiele wersji i każda z nich inaczej wybiera oś pionową.

Polecenie partition() jest prawdopodobnie najważniejszą częścią szybkiego sortowania. Cele partycji otrzymują tablicę wraz z elementem tablicy x jako pivot. Należy umieścić element x na właściwej pozycji, czyli w posortowanej tablicy, a następnie umieścić przed nim elementy mniejsze od x. Na końcu należy umieścić elementy większe od x. Na koniec trzeba umieścić po nim elementy większe od x. Upewnij się, że wszystko to zrobisz w czasie liniowym.

Warto też pamiętać, że szybkie sortowanie tworzy partycje w tablicach, po czym dwukrotnie wywołuje siebie w powtórzeniu, aby posortować powstałe w ten sposób podtarcze. Taki algorytm jest niezwykle przydatny w przypadku dużych zbiorów danych. Dzieje się tak dlatego, że jego złożoność w najgorszym przypadku wynosi O(n2). Dwa początkowe wyrażenia służą do wywołań rekurencyjnych, natomiast ostatnie wyrażenie jest przydatne w procesie partycjonowania. Elementy mniejsze od pivota są reprezentowane przez k.

Czas, jaki zajmuje szybkie sortowanie, zależy od strategii partycjonowania oraz od tablicy wejściowej.

Trzy przypadki szybkiego sortowania

Podobnie jak wiele innych algorytmów sortowania, również szybkie sortowanie ma swoje scenariusze przypadków. Omówimy je poniżej:

Najgorszy przypadek

Ten typ przypadku ma miejsce, gdy proces partycjonowania wybiera najmniejszy lub największy element jako punkt obrotu. Biorąc pod uwagę omówioną wcześniej strategię partycjonowania, w której za każdym razem jako punkt obrotu wybierany jest ostatni element, najgorszy scenariusz wystąpi, gdy tablica zostanie posortowana w porządku malejącym lub rosnącym. Rekurencja dla najgorszego przypadku jest następująca:

T(n) = T(0) + T(n-1) + (n)co jest równoważne T(n) = T(n-1) + (n)

Najlepszy przypadek

Najlepszy przypadek ma miejsce wtedy, gdy w procesie podziału jako punkt obrotu wybierany jest element środkowy. Rekurencja dla najlepszego przypadku jest następująca:

T(n) = 2T(n/2) + (n)

Przypadek średni

Należy rozważyć każdą permutację tablicy i obliczyć czas, jaki każda permutacja zajmuje na przeprowadzenie analizy przypadków. Oczywiście proces ten może być dość skomplikowany, nawet dla doświadczonych programistów. Uwzględnienie przypadku, gdy w partycji znajduje się O(n/9) elementów wraz z O(9n/10) elementów, pozwala oszacować średni przypadek. W tym przypadku rekurencja jest następująca.

T(n) = T(n/9) + T(9n/10) + (n)

Najczęstsze pytania zadawane na temat szybkiego sortowania

Istnieje wiele pytań dotyczących sortowania szybkiego, ale te wymienione poniżej są prawdopodobnie najczęstsze:

Czy szybkie sortowanie jest stabilnym algorytmem?

Cóż, domyślna implementacja szybkiego sortowania nie jest stabilna. Można jednak dodać stabilność do algorytmów sortowania, traktując indeks jako parametr porównania.

Co to jest trójdrożne szybkie sortowanie?

W przypadku zwykłego algorytmu szybkiego sortowania wybieramy element, który będzie pełnił rolę pivota, tworząc partycję w tablicy. Następnie wykonujemy rekurencję dla tablic podrzędnych znajdujących się po prawej i lewej stronie punktu obrotu.

Czy Quick Sort jest algorytmem in-place?

Zgodnie z szeroką definicją algorytmu in-place, szybkie sortowanie rzeczywiście zalicza się do tego typu algorytmów sortujących. Dzieje się tak, ponieważ wykorzystuje on dodatkową przestrzeń do przechowywania wywołań funkcji rekurencyjnych. Nie manipuluje jednak w żaden sposób danymi wejściowymi.

Szybszy niż większość algorytmów sortujących

Nie da się zaprzeczyć, że złożoność czasowa sortowania szybkiego w najgorszym przypadku wynosi O(n2), czyli więcej niż sortowania sterty, sortowania scalającego i wielu innych algorytmów sortujących, ale tak się składa, że sortowanie szybkie jest niewiarygodnie szybkie. Jednym z powodów jest to, że można efektywnie zaimplementować jego wewnętrzną pętlę w wielu typach danych i architektur świata rzeczywistego.
Co więcej, szybkie sortowanie można zaimplementować na wiele sposobów, po prostu zmieniając wybór punktu obrotu. Minimalizuje to występowanie najgorszego przypadku dla dowolnego typu danych. Programiści wolą jednak korzystać z sortowania łączonego, gdy danych jest zbyt wiele, zwłaszcza jeśli znajdują się one w zewnętrznej pamięci masowej.

Jak używać szybkiego sortowania w listach połączonych?

W przypadku list połączonych sprawa wygląda zupełnie inaczej ze względu na różnice występujące w alokacji pamięci w tablicy. Węzły list połączonych różnią się od węzłów tablic i często nie sąsiadują ze sobą w pamięci. Co więcej, listy połączone umożliwiają wprowadzanie elementów na środku, co nie jest możliwe w przypadku tablic. W takich scenariuszach programiści wolą używać sortowania scalającego, ponieważ okazuje się ono bardziej opłacalną opcją w porównaniu z sortowaniem szybkim.

Dlaczego programiści wolą sortować tablice za pomocą szybkiego sortowania?

Szybkie sortowanie jest prostym sortowaniem in-place, co oznacza, że nie wymaga dodatkowej pamięci. Z drugiej strony, sortowanie scalone wymaga O(N) dodatkowej pamięci. Dla tych, którzy się zastanawiają, N oznacza rozmiar tablicy, która może być bardzo duża. Odalokowanie i przydzielenie dodatkowej przestrzeni potrzebnej do sortowania scalającego zwiększa czas działania algorytmu.

Gdy porównamy średnią złożoność, łatwo zauważyć, że średnia złożoność obu typów sortowania wynosi O(NlogN). Jednak ich stałe różnią się od siebie. Jeśli chodzi o tablice, sortowanie przez scalanie nie jest skuteczne, ponieważ wykorzystuje dodatkową przestrzeń dyskową O(N). Najbardziej praktyczne implementacje szybkiego sortowania wykorzystują wersję randomizowaną. Średnia złożoność czasowa tej wersji wynosi O(nLogn). Warto również pamiętać, że w przypadku wersji randomizowanej istnieje możliwość wystąpienia gorszego przypadku. Nie ujawnia się to jednak w przypadku specyficznych wzorców, takich jak posortowana tablica.

Algorytm szybkiego sortowania jest dość przyjazny dla pamięci podręcznej ze względu na doskonałą lokalizację odniesienia, zwłaszcza gdy wykorzystuje się go dla tablic. Co więcej, szybkie sortowanie jest również rekurencyjne względem ogona, co oznacza, że należy wykonać optymalizacje wywołania ogonowego.