• Sortowanie odbywa się w dwóch fazach: dzielenia i sortowania
• W fazie dzielenia tablica jest dzielona na dwie części wokół pewnego elementu (nazywanego elementem centralnym).
• Wybieramy jeden element (losowo, choć może to być element środkowy), który nazwiemy $x$.
• Przeglądamy tablicę od lewej strony, aż znajdziemy element $a_i \geq x$, a następnie przeglądamy tablicę od prawej strony, aż znajdziemy element $a_j \leq x$.
• Zamieniamy miejscami elementy $a_i$ i $a_j$ i kontynuujemy proces przeglądania i zamiany, aż gdzieś w środku tablicy nastąpi spotkanie.
• W rezultacie otrzymujemy tablicę podzieloną na lewą część z wartościami mniejszymi od $x$ i na prawą część z wartościami większymi od $x$.
• Na tym kończy się faza podziały i rozpoczyna faza sortowania
• Faza sortowania zawiera dwa rekurencyjne wywołania tej samej funkcji sortowania: dla lewej i dla prawej części posortowanej tablicy.
• Rekurencja zatrzymuje się, gdy rozmiar tablicy do posortowania wynosi 1 (pojedynczy element na pewno jest posortowany).

Sortujemy 6-elementową tablicę tab:

Wywołanie funkcji QuickSort() ma postać QuickSort(tab, 0, 5)

Przykład - dla QuickSort(tab, 0, 5)

• wyznaczamy element środkowy: $\lfloor (0+5)/2 \rfloor = 2$, $x = tab[2] = 5$
• od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:
  
• poszukiwania kończymy, gdy indeksy mijają się:
  
• wywołujemy rekurencyjnie funkcję QuickSort() dla elementów z zakresów $[l,j]$ oraz $[i,r]$: QuickSort(tab, 0, 3), QuickSort(tab, 4, 5)

Przykład - dla QuickSort(tab, 0, 3)

• wyznaczamy element środkowy dla zakresu $[0,3]$: $(0+3)/2 = 1$, $x = tab[1] = 2$
• od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:
  
• poszukiwania kończymy, gdy indeksy mijają się:
  
• wywołujemy rekurencyjnie funkcję QuickSort() tylko dla elementów z zakresu $[2,3]$ (gdyż po lewej stronie rozmiar tablicy do posortowania wynosi 1 oraz $[i,r]$): QuickSort(tab, 2, 3)

Przykład - dla QuickSort(tab, 2, 3)

• wyznaczamy element środkowy dla zakresu $[2,3]$: $\lfloor (2+3)/2 \rfloor = 2$, $x = tab[2] = 3$
• od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:
  
• poszukiwania kończymy, gdy indeksy mijają się:
  
• rozmiar obu tablic do posortowania wynosi 1, więc nie ma nowych wywołań

Przykład - dla QuickSort(tab, 4, 5)

• wyznaczamy element środkowy dla zakresu $[4,5]$: $\lfloor (4+5)/2 \rfloor = 4$, $x = tab[4] = 6$
• od lewej szukamy $tab[i] \geq x$, a od prawej $tab[j] \leq x$, zamieniamy elementy miejscami:
  
• poszukiwania kończymy, gdy indeksy mijają się:
  
• rozmiar obu tablic do posortowania wynosi 1, więc nie ma nowych wywołań

Zalety:

• wysoka efektywność dla średniego przypadku

Wady:

• bardzo mała efektywność dla najgorszego przypadku
• duże zasoby zajmowane w trakcie pracy (bo: wywołania rekurencyjne zajmują pamięć komputera)
• brak stabilności

Powrót do głównej treści laboratorium