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): $\mathrm{\Theta }(n^2)$‍. Jednak średni czas przebiegu jest równie dobry jak w merge sort: $\mathrm{\Theta }(n{\log }_{2}n)$‍. 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.