Pseudokod sortowania quick sort

Przeanalizujmy pseudokod sortowania quick sort:

funkcja sortowanieSzybkie(tablica, p, k)
	jeżeli p < k wykonaj:
    	q = podziałTablicy(tablica, p, k)
        sortowanieSzybkie(tablica, p, q)
        sortowanieSzybkie(tablica, q + 1, k)

• p to miejsce, od którego chcemy posortować tablicę; gdy chcemy wykonać sortowanie od początku tablicy, to p = 1,

• k to miejsce zakończenia sortowania,

• q to punkt podziału tablicy.

Rozpoczynamy funkcję sortowanieSzybkie dla całej tablicy, którą chcemy posortować. Jeżeli p jest mniejsze od k, czyli tablica składa się z więcej niż jednego elementu, to wykonujemy następujące czynności. Wywołujemy funkcję podziałTablicy, która dzieli tablicę na dwie podtablice, a punkt podziału zapisuje w zmiennej q. Teraz rekurencyjnie wywołujemy funkcję sortowanieSzybkie dla podtablic. Algorytm kończy działanie, gdy w wyniku podziału pozostaną tablice jednoelementowe.

Pseudokod funkcji podziałTablicy wygląda następująco:

funkcja podziałTablicy(tablica, p, k)
	pivot = tablica[k]
    i = p 
	j = k 
    dopóki prawda wykonuj:
    	dopóki i <= k oraz tablica[i] < pivot
        	wykonuj i = i + 1
        
        dopóki j >= p oraz tablica[j] > pivot
            	wykonuj j = j - 1
        
        jeżeli i <= j wykonaj:
        	zamień tablica[i] z tablica[j]
            i = i + 1
            j = j - 1
		w przeciwnym razie wykonaj:
            zwróć j

• Za pomocą zmiennej pivot zapisujemy liczbę, która odpowiada za to, w której podtablicy umieścimy każdy z elementów. Jeżeli rozpatrywana liczba będzie mniejsza od pivot, umieścimy ją w tablicy pierwszej, jeżeli większa, to w drugiej, a jeżeli równa, to może pojawić się zarówno w pierwszej, jak i drugiej. Zmienna pivot może być dowolnym elementem tablicy, np. pierwszym, ostatnim lub środkowym. My wybraliśmy ostatni element.

• Następnie w zmiennych i oraz j zapisujemy miejsca przed pierwszym oraz za ostatnim elementem tablicy, którą chcemy posortować.

• Zwiększamy wówczas indeks i, do momentu znalezienia elementu tablicy większego niż pivot. Indeks j zmniejszamy, aby w końcu znaleźć element mniejszy od pivot.

• Po znalezieniu mniejszego elementu zmieniamy te elementów, aby uzyskać w podtablicach odpowiednie wartości.

• Wymienione dwa punkty, opisujące czynności zamiany, wykonujemy do momentu, gdy i osiągnie wartość większą niż j.

• W tym momencie funkcja zwraca indeks j, czyli punkt podziału tablicy.