Algorytm Szybkie sortowanie (ang. quicksort) to jeden z najpowszechniej używanych obecnie algorytmów sortujących. Jego złożoność wynosi dla większości przypadków . Jednak jego złożoność pesymistyczna wynosi . Są to jednak przypadki bardzo skrajne i z reguły bardzo rzadko występują.
Zasada działania opiera się na technice "dziel i zwyciężaj" - wstępna tablica jest dzielona na dwie podtablice na podstawie elementu środkowego r. Wszystkie elementy mniejsze od r, a po prawej stronie wszystkie większe bądź równe. Później każda z tablic jest sortowana oddzielnie, aż do uzyskania tablic jednoelementowych, których już nie trzeba sortować. Zastosowana technika polega na zastosowaniu tej samej techniki sortowania do każdej kolejnej rozpatrywanej tablicy.
Jeśli wylosowany element okaże się skrajnym tj. elementem, który powinien być na początku / końcu sortowanej tablicy to złożoność może osiągnąć wspomniane pesymistyczne . Z tego powodu często stosuje się dodatkowo algorytm, który szuka mediany na liście. W ten sposób złożoność jest zawsze gwarantowana, ponieważ w jednej i drugiej podliście zawsze znajdzie się tyle samo elementów (albo jeden mniej lub więcej zależy od rozpatrywanej listy).
Quicksort jest algorytmem natywnie zaimplementowanym w języku C++. Służy tego funkcja sort() w bibliotece algorithm.
Przyjmijmy, że do posortowania jest tablica L={5, 1, 3, 7, 2}. W celu wyjaśnienia wartości zostaną umieszczone w tabelce. Na początku należy wyznaczyć tzw. pivot. Jest to element odniesienia według, którego elementy trafią na prawo lub lewo. Pivot to zazwyczaj środkowy element, albo mediana. W tym przypadku pivotem będzie element środkowy 3:
| 5 | 1 | 3 | 7 | 2 |
Kolejny krok polega na pozamienianiu elementów tak, aby po lewej stronie znalazły się wszystkie elementy mniejsze od pivota, a na prawo większe (lub równe). Do przeprowadzenia tej operacji potrzebne są dwa indeksy: i oraz j. Pierwszy indeks i będzie szukał po lewej stronie, od początku elementu do zamiany, a j od końca, od prawej strony listy:
| 5 | 1 | 3 | 7 | 2 |
Pierwszy i ostatni element są na niewłaściwych pozycjach. Z tego powodu należy je zamieniać miejscami, a następnie zwiększyć indeks i oraz zmniejszyć indeks j. Po tym należy ponownie porównać kolejną parę elementów wskazywanych przez indeksy:
| 2 | 1 | 3 | 7 | 5 |
Wskazywane elementy znajdują się po dobrych stronach. W tym momencie indeksy i oraz j wskazują pivota. Teraz kolejny krok polega na posortowaniu dwóch tablic. Pierwsza ma zakres [1, i], a druga [j, n]. Dla każdej z tablic wykonywane są te same operacje co dla pierwszej:
| 2 | 1 | 3 |
Element na pozycji j jest na właściwej pozycji, ale element 2 nie jest, dlatego nie jest zwiększany indeks i, ale jest zmniejszany indeks j:
| 2 | 1 | 3 |
Po zamianie otrzymana jest podtablica [1, 2, 3]. Program o tym nie wie, dlatego wykona jeszcze sortowanie podtablicy [2, 3], a sortowanie podtablic jednoelementowych pominie. Teraz algorytm przechodzi do drugiej podtablicy listy podanej na wejściu:
| 3 | 7 | 5 |
Tym razem to element 5 jest na złej pozycji, dlatego w celu znalezienia pary, aby zamienić element zmniejszony zostanie indeks j. Potem jak w przypadku poprzedniej tablicy tablica zostanie podzielona na [3] i [5 7] i każda zostanie posortowana. Tylko w ten sposób istnieje gwarancja, że tablica zostanie posortowana. Sprawdzanie czy tablica jest już posortowane zwalniało by tylko algorytm.
Na koniec zestawienie posortowanych dwóch podtablic pokazuje, że sort(L) to [1, 2, 3, 5, 7].
Do implementacji przyda się funkcja zamieniająca wartości miejscami swap():
Mają powyższą funkcję można przystąpić do pisania kodu funkcji sortującej quicksort():
Jest to wersja rekurencyjna szybkiego sortowania, dlatego funkcja musi znać: l - wskaźnik na listę elementów, left i right - rozpatrywany zakres tablicy [left, right]. (2.) Ustalenie indeksów i oraz j. (2.) Wyznaczenia pivota - elementu odniesienia. (3.) Poszukiwania par do zamiany trwają, aż i <= j: (4. - 5.) poszukiwanie "niewłaściwego" elementu po lewej stronie oraz (6. - 7.) poszukiwanie niewłaściwego elementu w drugiej części. (8.) W przypadku wyznaczenia pary do zamiany i różnych indeksów: (9.) elementy są zamieniane i (10. - 11.) indeksy są odpowiednio zmieniane. (14. - 15.) Na sam koniec należy rekurencyjnie wywołać sortowanie podlist - zastosowane warunki uniemożliwiają sortowania tablic o mniej niż dwóch elementach.
Kod można przetestować przy pomocy poniższej funkcji main(). Warto zwrócić uwagę na to, że przy pierwszym wywołaniu należy podać jako left 0, a jako right n-1.
Zmień funkcję quicksort() tak, aby sortowała listę malejąco.
Ułatw korzystanie z funkcji quicksort() poprzez dodanie przeciążenia funkcji quicksort(). Jedyny wymaganymi elementami powinna być wskaźnik na listę liczb l oraz n - ile ma elementów.