|
O mojí osobě
Něco ke stažení Články a návody Poezie Odkazy |
Quick sort je asi nejčastěji používaným třídícím algoritmem. Jeho výhodou je velká rychlost třídění - v průměrném případě má časovou náročnost O(n*log n), v nejhorším O (n^2). V nejhorším případě má sice horší asymptotický čas než Mergesort, který slibuje i v nejhorším případě čas o(n*log n), ovšem v praxi se osvědčil mnohem lépe. Myšlenka Quick sortu je celkem snadná - v jednom kroku se vybere prvek (pivot) z pole, které se podle něho rozdělí na prvky větší a prvky menší. Obě nové části se setřídí rekurzivním voláním Quicksortu a výsledky se spojí s pivotem do výsledného pole. Při implementaci tohoto algoritmu je velmi důležitá volba pivota. V případě, že volíme pivota špatně, algoritmus bude pracovat v nejhorším možném čase O(n^2). To nastane v případě, že za pivota budeme volit prveky největší nebo nejmenší z tříděné posloupnosti. Důvodem je to, že při rekurzivním volání bude jedno z nových polí prázné, a druhé bude obsahovat pouze o jeden prvek méně. Nejlepším pivotem by byl medián (prostřední hodnota) posloupnosti. Lze si tak vždy asymptotickou složitost O (n*log n). Protože ale algoritmus na hledání mediánu v lineárním čase je celkem pomalý (vzhledem k dalším metodám), v praxi se mnohem častěji používají snadnější metody - pivota můžeme zvolit např. jako první prvek posloupnosti, nebo můžeme vybrat 3 náhodné prvky a za pivota prohlásit prostředního z nich co do hodnoty. Samotný algoritmus tedy vypadá nějak takto:
QuickSort(Pole)
{
pivot=VyberPivota(Pole);
Rozdel(Pole, pivot, mensi, vetsi);
/*
prvky z Pole se rozdeli podle pivota do poli mensi a vetsi
*/
QuickSort(mensi);
Quicksort(vetsi);
Pole=Zretez(mensi,pivot,vetsi);
//spoji pole mensi s pivotem a polem vetsi a vrati to
return Pole;
}
V předchozím algoritmu používáme pomocná pole mensi a vetsi. Ačkoliv to nemusí být na první pohled vidět celkem nám zaberou paměť o velikosti n^2. To protože budou vytvořena při každém rekurzivním volání algoritmu. Lepšího výsledku dosáhneme, když místo polí budeme předávat algoritmu pouze indexy do pole Pole, kde začíná/končí oblast mensi a oblast vetsi.
void Rozdel(int ipivot,int zacatek,int konec,int *z2,int *k1)
{
int i,j;
int pivot,prvek;
pivot=Pole[ipivot];
j=konec;
i=zacatek;
Pole[ipivot]=Pole[i];
//pivot schovame na zacatek
Pole[i]=pivot;
i++;
while (i< j)
{
while ((Pole[i]< =pivot)&&(i< j)) i++;
while ((Pole[j]> pivot)&&(i< j)) j--;
prvek=Pole[i]; //prohozeni
Pole[i]=Pole[j];
Pole[j]=prvek;
};
Pole[zacatek]=Pole[j];
//dam pivota mezi nove pole
Pole[j]=pivot;
z2=j+1;
k1=j-1;
return;
};
void QuickSort(int zacatek, int konec)
{
int z2,k1;
int ipivot;
ipivot=IndexPivota(zacatek, konec); //vrati index pivota
Rozdel(ipivot, zacatek, konec,&& z2, && k1);
/*
prvky z Pole mezi zacatek a konec se rozdeli podle
pivota a vrati se indexy zacatku a koncu oblasti s
mensimi a vetsimi prvky
*/
QuickSort(zacatek,k1);
Quicksort(z2,konec);
/*
v poli se nemusi nic zretezovat
- vse lezi spravne za sebou
*/
}
A takhle vypadá elegantní řešení v Haskellu (za pivota se bere první prvek vstupního pole). qsort [] = [] qsort (x:xs) = qsort [y | y < - xs, y< x] ++ [x] ++ qsort [y | y < - xs, y> =x] |