|
O mojí osobě
Něco ke stažení Články a návody Poezie Odkazy |
Přihrádkové třídění Přihrádkové třídění je šikovný třídící algoritmus, který se dá použít pro třídění celých čísel v omezeném rozsahu. Jeho výhodou je velká rychlost, asymptotická složitost tohoto algoritmu je O(n+m), kde n je počet tříděných prvků a m délka intervalu, ze kterého tříděná čísla mohou pocházet. Tato rychlost je ale vyvážena tím, že je omezen pouze na celá čísla a není tedy tak univerzální jako ostatní třídící algoritmy. Jeho idea je následující: Předpokládejme, že chceme setřídit celá čísla v rozsahu 1 .. k ležící v poli A (o n prvcích). Pak si vytvoříme pomocné pole B o velikosti k, kam spočtem na pozici B[x] počet výskytů hodnoty x v poli A. V dalším kroku nám stačí projít pole B od začátku (třídíme-li od nejmenších prvků) a zapsat do A tolik prvků x, kolik je hodnota B[x].
void Prihradkove_trideni(int *pole)
{
int B[MAX_HODNOTA+1];
int i,j;
for (i=0;i< MAX_HODNOTA+1;i++)
B[i]=0;
for (i=0;pole[i];i++)
B[pole[i]]++; //spoctu pocet vyskytu hodnot
j=0;
for (i=0;i< MAX_HODNOTA+1;i++)
{
while (B[i]> 0) //zapisuju hodnotu podle poctu vyskytu
{
pole[j]=i;
B[i]--;
j++;
};
};
};
Toto je jednodušší verze - může se nám totiž stát, že máme setřídit nějaké složitější struktury. Ty mohou kromě klíče, podle kterého třídíme, obsahovat i další informace, které nesmíme ztratit. Příkladem může být třídění záznamů o čtenářích v knihovně podle čísla průkazky. Pro řešení tohoto problému stačí náš algoritmus jen malinko upravit:
Nejprve si do pole B spočtu počet výskytů všech hodnot (stejně jako v předchozím případě). Spočtu si pro každou hodnotu, do kterého indexu budou ve výsledném poli uloženy záznamy této hodnoty (opravdu "do kterého", spočte se to snadněji, než "od kterého"). Na to nám stačí projít pole B od 2. do posledního prvku a přičíst ke každé položce hodnotu položky s indexem o jedna menším. Nakonec projdeme v jednom cyklu od posledního k prvnímu prvku pole A. Vezmeme prvek z pole A, například x, podíváme se do B(x) na index, kam ho máme uložit a uložíme ho do pole C(B(x)). Pak snížíme hodnotu B(x) o jedna a zpracujeme další prvek. To, že poslední cyklus provádíme od konce, nám zaručí stabilitu třídícího algoritmu. To znamená, že když v původním poli ležel jeden prvek s hodnotou x před jiným prvkem se stejnou hodnotou, bude ve výsledném poli také ležet před tím druhým. To nám umožní třídit podle více kritérií - pokud budeme chtít setřídit již zmíněné čtenáře v knihovně podle věku a ty stejně staré třeba podle počtu výpůjček, použijeme nejprve algoritmus na setřídění podle výpůjček a pak výsledek setřídíme podle věku - stejně staří čtenáři si zachovají předchozí uspořádání. Trik s několikanásobným tříděním se nám může hodit i pro jiné problémy. Můžeme mít za úkol například setřídit 100 celých čísel o 10 číslicích. Kdybychom postupovali podle první verze algoritmu, potřebovali bychom pomocné pole B o velikosti miliardy bytů - a to ani při dnešních velikostech pamětí není reálné. Místo toho ale můžeme těch 100 číslic třídit postupně - neprve všechny setřídit podle poslední číslice, pak podle předposlední,... Podle uvedné vlastnosti stability tak získáme správný výsledek a pole B bude mít velikost pouze 10. Zrychlí se i výpočet. Algoritmus se sice bude spouštět 10 krát, ale ušetříme spoustu času na procházení pole B. |