User Tools
dydaktyka:aisd:2016:sort_quick-sort
Differences
This shows you the differences between two versions of the page.
|
dydaktyka:aisd:2016:sort_quick-sort [2016/05/25 15:36] pkleczek utworzono |
— (current) | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Sortowanie metodą quick-sort ====== | ||
| - | ===== Algorytm metody ===== | ||
| - | |||
| - | * 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). | ||
| - | |||
| - | ===== Przykład ===== | ||
| - | |||
| - | Sortujemy 6-elementową tablicę ''tab'':\\ {{:dydaktyka:aisd:2016:quick-sort_example_01.png?nolink|}} | ||
| - | |||
| - | 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:\\ {{:dydaktyka:aisd:2016:quick-sort_example_02.png?nolink|}} | ||
| - | * poszukiwania kończymy, gdy indeksy mijają się:\\ {{:dydaktyka:aisd:2016:quick-sort_example_03.png?nolink|}} | ||
| - | * 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:\\ {{:dydaktyka:aisd:2016:quick-sort_example_04.png?nolink|}} | ||
| - | * poszukiwania kończymy, gdy indeksy mijają się:\\ {{:dydaktyka:aisd:2016:quick-sort_example_05.png?nolink|}} | ||
| - | * 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:\\ {{:dydaktyka:aisd:2016:quick-sort_example_06.png?nolink|}} | ||
| - | * poszukiwania kończymy, gdy indeksy mijają się:\\ {{:dydaktyka:aisd:2016:quick-sort_example_07.png?nolink|}} | ||
| - | * 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:\\ {{:dydaktyka:aisd:2016:quick-sort_example_08.png?nolink|}} | ||
| - | * poszukiwania kończymy, gdy indeksy mijają się:\\ {{:dydaktyka:aisd:2016:quick-sort_example_09.png?nolink|}} | ||
| - | * rozmiar obu tablic do posortowania wynosi 1, więc nie ma nowych wywołań | ||
| - | |||
| - | ===== Uwagi ===== | ||
| - | |||
| - | 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 | ||
| - | |||
| - | |||
| - | ---- | ||
| - | |||
| - | [[dydaktyka:aisd:2016:sort|Powrót do głównej treści laboratorium]] | ||
dydaktyka/aisd/2016/sort_quick-sort.1464183385.txt.gz · Last modified: 2020/03/25 11:46 (external edit)
Page Tools
