Szybkie sortowanie (quicksort)

Podobnie jak sortowanie przez scalanie merge sort, quicksort korzysta z techniki dziel i zwyciężaj, zatem jest to algorytm rekurencyjny. Quicksort korzysta ze strategii dziel i zwyciężaj w nieco inny sposób niż merge sort. W merge sort w kroku podziału niemal nic się nie dzieje, a prawdziwa praca odbywa się podczas scalania. W quicksort jest odwrotnie: cała filozofia zawiera się w części odpowiedzialnej za podział. Tak naprawdę, w kroku scalania, quicksort nie robi nic.

Quicksort różni się od merge sort także w kilku innych aspektach. Quicksort pracuje w miejscu. Jego pesymistyczny czas działania jest taki, jak w przypadku sortowania przez wybór (selection sort) czy przez wstawianie (insertion sort): $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Jednak średni czas przebiegu jest równie dobry jak w merge sort: $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis. Dlaczego zatem brać pod uwagę quicksort podczas gdy merge sort jest przynajmniej tak samo dobry? Otóż stały współczynnik ukryty w notacji dużego-Θ jest dla quicksort całkiem przyzwoity. W praktyce, quicksort ma lepszą wydajność niż merge sort i osiąga zauważalnie lepsze rezultaty niż sortowanie przez wybór czy przez wstawianie.

Wyjaśnimy jak quicksort wykorzystuje strategię dziel-i-rządź (divide-and-conquer). Podobnie jak w przypadku merge sort, załóżmy, że chcemy posortować podtablicę array[p..r], zakładając na początku, że nasza tablica to array[0..n-1].

Podstawowymi przypadkami są tablice o mniej niż dwu elementach, tak jak w sortowaniu przez złączanie (merge sort). W sortowaniu przez złączanie, nie spotyka się pod-tablicy bez elementów, ale w quicksort może się tak zdarzyć, jeżeli pozostałe elementy pod-tablicy są wszystkie mniejsze lub wszystkie większe niż piwot.

Cofnijmy się do drugiego kroku i prześledźmy rekurencyjne sortowanie pod-tablic. Po pierwszym podziale, mamy pod-tablice [5, 2, 3] i [12, 7, 14, 9, 10, 11], z 6 jako piwotem.

Aby posortować pod-tablicę [5, 2, 3], wybieramy 3 jako piwot. Po podziale mamy [2, 3, 5]. Pod-tablica [2], po lewej stronie piwotu, jest podstawowym przypadkiem, podobnie jak pod-tablica [5] po prawej.

Aby posortować pod-tablicę [12, 7, 14, 9, 10, 11], wybieramy 11 jako piwot, co daje w rezultacie [7, 9, 10] po lewej stronie piwotu i [14, 12] po prawo. Po posortowaniu tych pod-tablic, otrzymujemy kolejno [7, 9, 10], 11, [12, 14].

Poniżej zaprezentowano cały przebieg algorytmu quicksort. Na niebiesko zaznaczono miejsca, gdzie były piwoty w poprzednich przebiegach rekurencji, zatem wartości w tych miejscach już nie będą sprawdzane ani przenoszone:

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.