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 - 1
	j = k + 1
    dopóki prawda wykonuj:
    	wykonuj i = i + 1
        	dopóki i <= k oraz tablica(i) < pivot
        wykonuj j = j - 1
        	dopóki j >= p oraz tablica(j) > pivot
        jeżeli i <= j wykonaj:
        	zamień tablica(i) z tablica(j)
		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.