Rýchle triedenie

Táto stránka obsahuje opis postupu pri implementácii algoritmu rýchleho triedenia (anglicky quick sort). Dá sa povedať, že táto stránka nadväzuje na reťaz stránok s opisom implementácie iných algoritmov, posledným bol algoritmus triedenia výberom. Je totiž vhodné, keď sa pred štúdiom tejto stránky budete zaoberať pochopením uvedených algoritmov.

Najskôr opíšme ako algoritmus rýchleho triedenia funguje. Algoritmus rýchleho triedenia vychádza z myšlienky, ktorá sa pokúša napodobniť nasledujúci intuitívny postup (samozrejme, že algoritmus to robí trošku efektívnejšie): Majme náhodne dlhý číselný rad. Za predpokladu, že triedime vzostupne (od najmenšieho prvku po najväčší) – rozdeľme ho na dve časti (nesúmerne) a zoberme ľubovoľný malý prvok z hornej časti číselného radu a súčasne veľký prvok zo spodnej časti radu. Vzájomne ich vymeňme. Opakujme to dovtedy, kým nie je rad čísiel zotriedený.

Prejdime k terminológii, ktorá je bližšie k programovaniu. Majme celočíselné pole. Chceme ho zotriediť vzostupne. Rozdeľme toto pole na dve časti (kritérium si povieme neskôr) a začnime ich prehľadávať. V „spodnej“ (ľavej) časti budeme hľadať prvý „veľký“ prvok (s vysokou hodnotou), v „hornej“ (pravej) časti zase prvý „malý“ prvok (s nízkou hodnotou). Vzájomne ich vymeňme. Toto opakujme až kým sa ukazovatele (indexy) prehľadávaní nepretnú. Zopakujme to pre každú „menšiu časť“ poľa, ktorá pri tom vznikne. Týmto postupom sa budú malé prvky postupne dostávať nižšie a veľké vyššie.

Zostáva spresniť to, ako pole rozdelíme a ako určíme tzv. „menšie časti“ poľa (v zmysle menších intervalov), pre ktoré budeme algoritmus vykonávať. Najlepšie by algoritmus fungoval vtedy, keby sme hodnoty prvkov poľa posudzovali podľa tzv. mediánu (stredná hodnota – rozdeľuje pole na dve rovnako početné časti). Lenže hľadanie mediánu by bolo výpočtovo také náročné, že by sa celá efektívnosť algoritmu stratila (v skutočnosti je najjednoduchším spôsobom na nájdenie mediánu zotriedenie poľa a vybratie prostredného prvku; lenže triedenie je predsa presne to, čo teraz robíme).

Preto sa v našej (a mnohých iných) implementácii jednoducho zoberie prvok, ktorý leží v strede prehľadávaného intervalu. Pozor, neznamená to, že tým rozdelíme interval na dve rovnaké polovice (to by sme dosiahli práve s pomocou mediánu). V skutočnosti ho rozdelíme veľmi neurčito: na „malé“ a „veľké“ hodnoty, pričom nevieme, kde presne ležia „malé“ alebo „veľké“ hodnoty. To sa ukáže až v priebehu vykonávania algoritmu.

Prvok, ktorým sa budeme riadiť (ten, ktorý vyberieme zo stredu poľa) sa nazýva pivot. Ako bolo naznačené vyššie: Náš pivot nebude rozdeľovať pole na dve rovnaké polovice, ale určí to, ktoré hodnoty budeme považovať za malé a ktoré za veľké. To, kde sa presne ukazovatele prehľadávaní pretnú, nie je nikdy vopred známe. Jednoducho sa zľava hľadajú hodnoty, ktoré sú väčšie alebo rovné pivotu a naopak.

Menšie prehľadávané intervaly poľa („menšie časti“ poľa) budeme určovať s pomocou hodnôt hraníc prehľadávaného intervalu a indexov prehľadávaní. Takže ide o vhodné porovnanie nasledujúcich štyroch hodnôt:

• spodná hranica prehľadávaného intervalu: lo – na začiatku rovná nule, čo je index prvého prvku poľa,
• horná hranica prehľadávaného intervalu: hi – na začiatku rovná hodnote o jedno menšie než je dĺžka poľa, čo je index posledného prvku poľa,
• index prehľadávania prvkov zľava: i – na začiatku stotožnená so spodnou hranicou intervalu,
• index prehľadávania prvkov sprava: j – na začiatku stotožnená s hornou hranicou intervalu.

Indexy prehľadávania (i a j) sa počas vykonávania algoritmu k sebe postupne približujú až kým sa prekrížia. Menšie prehľadávané intervaly potom určíme takto:

• Ak premenné lo a j vymedzujú aspoň dva prvky poľa (t. j. lo != j, resp. lo < j), tak hodnota lo bude nová spodná hranica prehľadávaného intervalu a j zase horná.
• Ak to isté platí pre premenné i a hi (v tomto poradí: i < hi), tak hodnota i bude nová spodná hranica a hodnota hi nová vrchná hranica intervalu.

Naša implementácia je rekurzívna. Keďže sú dve možnosti na určenie menšieho prehľadávaného intervalu, budú sa v zápise algoritmu vyskytovať dve rekurzívne volania, ktoré budú samozrejme podmienené.

Podobne ako pri predchádzajúcich triedeniach budeme napĺňať spočiatku prázdnu kostru programu:

~

public class QuickSort extends Konzola
{
	private int pole[] = new int[10];

	private QuickSort()
	{
		for (int i = 0; i < pole.length; ++i)
			pole[i] = (int)náhodnéCeléČíslo(1, 20);

		vypíšRiadok(pole);
		quickSort();
		vypíšRiadok(pole);
	}

	// Toto bude rekurzívna metóda rýchleho vyhľadávania:
	private void quickSort(int lo, int hi)
	{
		/*# Na tomto mieste budeme vytvárať algoritmus. */
	}

	/**
	 * Táto metóda spustí algoritmus rýchleho vyhľadávania na celom
	 * intervale poľa:
	 * od spodnej hranice (0 – prvý prvok poľa)
	 * po hornú (pole.length - 1 – posledný prvok poľa).
	 */
	public void quickSort()
	{
		quickSort(0, pole.length - 1);
	}

	/**
	 * Táto metóda vymení prvky poľa na pozíciách i a j.
	 */
	public void vymeň(int i, int j)
	{
		int c = pole[i];
		pole[i] = pole[j];
		pole[j] = c;
	}

	public static void main(String[] args)
	{
		new QuickSort();
	}
}

int stred = (lo + hi) / 2;
int pivot = pole[stred];

int pivot = pole[(lo + hi) / 2];

int i = lo, j = hi;

while (i <= j)
{
	// …

while (pole[i] < pivot) ++i; // vľavo „nechávam na pokoji“ malé prvky
while (pole[j] > pivot) --j; // vpravo „nechávam na pokoji“ veľké prvky

if (i <= j)
{
	vymeň(i, j);
	++i;
	--j;
}

vymeň(i, j);
++i;
--j;

vymeň(i++, j--);

if (i <= j) vymeň(i++, j--);

if (lo < j) quickSort(lo, j);

if (i < hi) quickSort(i, hi);

public void quickSort(int lo, int hi)
{
	int pivot = pole[(lo + hi) / 2];
	int i = lo, j = hi;

	while (i <= j)
	{
		while (pole[i] < pivot) ++i;
		while (pole[j] > pivot) --j;
		if (i <= j) vymeň(i++, j--);
	}

	if (lo < j) quickSort(lo, j);
	if (i < hi) quickSort(i, hi);
}