|
Quick Sort Główna idea: Głównym elementem algorytmu QuickSort jest funkcja "partition". Funkcja "partition" wywoływana jest dla całej tablicy lub jej fragmentu. Zwraca ona pewien punkt w danym fragmencie od którego wszystkie wcześniejsze elementy są mniejsze lub równe pierwszemu elementowi a wszystkie elementy za tym punktem są większe (chociaż jeszcze niekoniecznie posortowane). Oczywiście taki punkt nie musi istnieć od razu, toteż funkcja partition idąc z obu końców takiego fragmentu przestawia odpowiednie elementy. np.: tablica {5, 2, 7, 4, 8, 9, 3, 1, 6} po wykonaniu funkcji partition może wyglądać tak: {5, 2, 1, 4, |3|, 9, 8, 7, 6} (zostały zamienione '7' z '1' oraz '8' z '3'. Elementem granicznym jest '3' wszystkie elementy na lewo od '|' są mniejsze lub równe pierwszemu elementowi a elementy na prawo od '|' są większe) Funkcja "QuickSort" wywołuje rekurencyjnie funkcję "partition": najpierw dla całej tablicy, potem dla otrzymanych dwuch części, następnie dla każdej z kolejnych otrzymanych, itd. aż do momentu gdy otrzymany fragment tablicy będzie jedno lub 2 elementowy (taki fragment na pewno będzie posortowany). A zatem, skoro wszystkie jedno- lub dwu-elementowe fragmenty tablicy będą posortowane a jednocześnie (dzięki funkcji partition) wszystkie fragmenty wcześniejsze zawierają elementy mniejsze od elementów z fragmentów dalszych, to znaczy, że cała tablica jest w tym momencie posortowana.
void qSort(int[] tab, int l, int p)
{
int k = partition(tab, l, p);
if(k - 1 > l)
qSort(tab, l, k - 1);
if(k + 1 < p)
qSort(tab, k + 1, p);
}
int partition(int[] tab, int l, int p)
{
int gran = tab[l];
int i = l, j = p;
while(i < j)
{
while(i < p && tab[i] <= gran)
i++;
while(tab[j] > gran)
j--;
if(i < j && tab[i] > tab[j])
{
int x = tab[i];
tab[i] = tab[j];
tab[j] = x;
}
}
tab[l] = tab[j];
tab[j] = gran;
return j;
}
Wizualizacja:Zielony pionowy pasek pokazuje jaki fragment tablicy jest aktualnie poddawany funkcji "partition" Żółte przemieszczające się kropki pokazują elementy sprawdzane przez funkcję "partition" Gdy funkcja "partition" natrafi na elementy, które musi zamienić miejscami kropki zmieniają kolor na czerwony zatrzymując się jednocześnie przy tych elementach. Gdy funkcja "partition" skończy przestawianie elementów i wyznaczy miejsce podziału aktualnego fragmentu tablicy, pojawia się niebieska kropka przy elemencie będącym owym podziałem. powrót |
Strony uczelniane: Str. Główna SerwisStudencki Poczta Sekret BSS-HOWTO Hasło Biblioteka Index stron |