11 Triedenie
Triedenie (usporiadanie) množiny prvkov je proces preusporiadania danej množiny v špecifickom poradí (podľa určitej relácie). Je to jedna z najčastejšie sa vyskytujúcich operácií pri spracovaní údajov, resp. dátových štruktúr. Usporiadanie množiny prvkov výrazne zvyšuje efektívnosť vyhľadávania prvkov. Typickými príkladmi triedenia je spracovanie rôznych zoznamov, registrov, skladov, slovníkov a pod.
Problematika triedenia je veľmi prepracovaná. Venovalo sa jej množstvo autorov, za základnú publikáciu je považovaný [Knuth78]. Existuje celý rad metód, ktoré sa líšia rýchlosťou, pamäťovou a operačnou zložitosťou algoritmu, princípom triedenia, prípustným typom triedených prvkov a spôsobom prístupu k triedeným prvkom. Pre ilustráciu uvedieme najznámejšie metódy triedenia na príklade usporiadania množiny celých čísel od najmenšieho po najväčšie (relácia <=). Cieľom ilustrácie je uviesť algoritmy jednotlivých metód v jazyku C vo forme funkcií. Ich podrobnejší popis, zdôvodnenie aj vzájomné porovnanie môže čitateľ nájsť v literatúre [1], [2], [3] i [4]. Vstupným parametrom všetkých funkcií je pole celých čísel a ich počet, výstupom je zotriedené pole. V dvoch prípadoch (heapsort a mergesort) je vo funkciách vstupné pole transformované do pomocného poľa od indexu 1, pretože daný algoritmus s počiatočným indexom 0 nepracuje. V prípade funkcie mergesort má okrem toho pomocné pole dvojnásobnú dĺžku (vyplýva z metódy). Niektoré z uvádzaných algoritmov sú implementované priamo v prekladačoch jazyka C (napr. quicksort pod názvom qsort, binsearch pod názvom bsearch), pričom spôsob porovnávania prvkov je daný užívateľom definovanou funkciou (v závislosti na type prvkov množiny). Parametre týchto funkcií sú uvedené pri ich popise.
Všetky uvedené funkcie sú ilustrovanné v príklade p11_1.C Hlavný program obsahuje výpis celočíselného poľa pred triedením a po ňom a samozrejme volanie príslušnej funkcie. V uvedenom príklade je volaná funkcia insert, ktorá zabezpečí potrebné usporiadanie poľa a a následne funkcia binsearch, ktorá vráti index prvku (12) v usporiadanom (zotriedenom) poli. O jednotlivých funkciách sa stručne zmienime v poradí, v akom sú uvedené v príklade.
Bubblesort realizuje priamu výmenu dvoch prvkov množiny v zmysle zadanej relácie, pričom jeden cyklus porovnávania ide od začiatku, druhý od konca triedeného poľa. Názov metódy pochádza z analógie medzi pohybom triedených prvkov a pohybom bublín vo vode (ak uvažujeme triedené pole vo zvislej polohe).
Uvedený algoritmus je možné vylepšiť sledovaním, či pri jednotlivých prechodoch nastávajú výmeny prvkov pomocou indexov L a R vo funkcii shakersort, ktorá zabezpečuje triedenie pretriasaním. Triedenie je ukončené, keď sa indexy L a R stretnú. Ich počiatočné hodnoty sú začiatok a koniec triedeného poľa. Triedi sa pritom vždy len tá časť poľa, ktorá sa ešte môže meniť (v rozsahu L - R).
Funkcia insert realizuje triedenie priamym vkladaním, ktoré je založené na schopnosti vložiť daný prvok tak, že výsledná postupnosť je znovu zotriedená. Postup má tieto kroky: najprv sa nájde miesto, kde treba prvok vložiť, potom sa ostatné prvky o jedno miesto posunú a na takto získané miesto sa uloží daný prvok (analógia - usporiadanie hracích kariet).
Zlepšenie (pokiaľ ide o zrýchlenie metódy určenia miesta vkladania prvku) realizuje funkcia bininsert, ktorá používa na tento cieľ metódu binárneho hľadania (viď funkciu binsearch). Vychádzame pritom z predpokladu, že cieľová postupnosť je zotriedená.
Funkcia select realizuje triedenie priamym výberom, ktoré vychádza z predpokladu, že najmenší prvok prvok môžeme zaradiť priamo na začiatok triedeného poľa, najmenší prvok zo zvyšku poľa zase na jeho začiatok atď.
Zlepšenie triedenia priamym vkladaním navrhol v r. 1959 D.I. Shell - funkcia Shellsort. Toto pozostáva v triedení prvkov po skupinách so zmenšovaním kroku, pričom sa začína s najväčším krokom a končí krokom 1. Obvykle sa postupnosť krokov uvažuje ako rad mocnín 2, napr.: 4,2,1, ale nie je to podmienkou. Voľba postupnosti krokov však môže podstatne ovplyvniť efektívnosť triedenia.
Funkcia heapsort realizuje stromové triedenie (pomocou binárneho stromu), založené na opakujúcom sa výbere najmenšieho prvku zo všetkých n prvkov potom n-1 prvkov atď. Nevýhodou tohoto spôsobu sú zvýšené nároky na pamäť (minimálne dvojnásobok rozsahu triedeného poľa, ktoré sa zvyčajne realizujú tzv. haldou - anglicky heap, odtiaľ názov metódy).
Ďalšie zlepšenie triedenia výmenou, ktoré predstavuje najlepšiu metódu triedenia v poli, navrhol C.A.Hoare a nazval ju pre jej rýchlosť quicksort. Pod týmto názvom je metóda všeobecne známa (viď funkcia qsort v jazyku C). Vychádza zo skutočnosti, že najefektívnejšie sú výmeny prvkov na čo najväčšie vzdialenosti. Triedenie preto (podobne ako shakersort) začína z oboch koncov poľa a končí, keď sa indexy stretnú. Funkcia quicksort využíva rekuzrívnu triediacu funkciu qs, ktorá zotrieďuje jednotlivé časti triedeného poľa. Použitie rekurzie je veľmi účinná programovacia technika [4], ktorá je v tomto prípade úplne namieste (niekedy však môže zapríčiniť aj nepríjemné situácie - doporučujeme zvýšenú obozretnosť !).
Triedenie metódou priameho zlučovania - funkcia mergesort sa používa predovšetkým v prípadoch triedenia takých veľkých rozsahov údajov (ide o diskové, resp. iné periférne súbory), ktoré sa nezmestia do operačnej pamäte počítača. Triedenie pracuje takto: 1. postupnosť sa rozdelí na dve polovice, 2. ich prvky sa spájajú do usporiadaných dvojíc. 3. na takto vzniknutú postupnosť sa aplikujú kroky 1. a 2., čím dostaneme usporiadané štvorice. 4. opakovaním krokov 1. až 3. dostaneme osmice atď. Algoritmus končí usporiadaním celej postupnosti. Triedenie si vyžaduje pamäť rovnú dvojnásobku veľkosti poľa. V jednej polovici je zdrojová postupnosť, v druhej sa ukladá cieľová.
/* K13_1.c triedenie
metody
bubblesort priama vymena
shakersort pretriasanim
insert priamym vkladanim
bininsert binarnym vkladanim
select priamym vyberom
Shellsort vkladanim so
zmensovanim kroku
heapsort stromove - haldou
quicksort rozdelovanim
mergesort priamym zlucovanim
vyhladavanie
binsearch binarne hladanie
*/
#include <stdio.h>
#include <alloc.h>
void bubblesort(int pole[], int pocet);
void shakersort(int pole[], int pocet);
void insert(int pole[], int pocet);
void insert1(int pole[], int pocet);
void bininsert(int pole[], int pocet);
void select(int pole[], int pocet);
void Shellsort(int pole[], int pocet);
void heapsort(int pole[], int pocet);
void quicksort(int pole[], int pocet);
void mergesort(int pole[], int pocet);
int binsearch(int pole[], int pocet, int cislo);
main()
{
int a[32]={44,55,12,42,94,18,06,67,1,3,3,13,48,56,59,33},i;
printf("\nBegin\n");
for(i=0;i<16;i++)printf("%3d ",a[i]);
insert(a,16);
i=binsearch(a,16,12);
printf("\nResult 12 je a[%d]\n",i);
for(i=0;i<16;i++)printf("%3d ",a[i]);
return 0;
}
void bubblesort(int pole[], int pocet)
/* bublinove triedenie - priamou vymenou */
{
int a,b,pom;
for(a=1; a<pocet; ++a)
for(b=pocet-1; b>=a; --b)
if(pole[b-1] > pole[b]){ /* vymena */
pom = pole[b-1];
pole[b-1] = pole[b];
pole[b] = pom;
}
}
void shakersort(int pole[], int pocet)
/* triedenie pretriasanim - priamou vymenou */
{
int a,b,L,R,pom;
L=1; R=b=pocet-1;
do{
for(a=R; a>=L; a--)
if(pole[a-1] > pole[a]){
pom = pole[a-1];
pole[a-1] = pole[a];
pole[a] = pom;
b=a; /* index vymeny lavy */
}
L = b+1;
for(a=L; a<R+1; a++)
if(pole[a-1] > pole[a]){
pom = pole[a-1];
pole[a-1] = pole[a];
pole[a] = pom;
b=a; /* index vymeny pravy */
}
R = b-1;
} while(L<=R); /* kym sa nestretnu */
}
void insert1(int pole[], int pocet)
/* triedenie priamym vkladanim - verzia s kopiou */
{
int a,b,pom,*ppole;
ppole=malloc(pocet+1); /* pom. pole */
for(a=0;a<pocet;a++)
ppole[a+1]=pole[a]; /* od 1 po pocet */
for(a=1; a<=pocet; a++){
pom = ppole[a];
ppole[0] = pom; /* na 0 minimum */
b = a;
while(pom < ppole[b-1]){
ppole[b] = ppole[b-1];
b--;
}
ppole[b] = pom; /* vymena */
};
for(a=0;a<pocet;a++)
pole[a]=ppole[a+1];
free(ppole);
}
void insert(int pole[], int pocet)
/* triedenie priamym vkladanim */
{
int a,b,pom,*ppole;
for(a=1; a<pocet; a++){
pom = pole[a];
b = a;
while(b>0 && pom < pole[b-1]){
pole[b] = pole[b-1];
b--;
}
pole[b] = pom; /* vymena */
};
}
void bininsert(int pole[], int pocet)
/* triedenie binarnym vkladanim */
{
int a,b,pom,m,L,R;
for(a=1; a<pocet; a++){
pom = pole[a];
L = 0; R = a;
while(L < R){ /* najst miesto pre prvok */
m = (L+R)/2;
if(pole[m] <= pom)
L = m+1;
else
R = m;
}
for(b=a;b>=R+1;b--) /* uvolnit miesto pre prvok */
pole[b]=pole[b-1];
pole[R]=pom;
}
}
void select(int pole[], int pocet)
/* triedenie priamym vyberom */
{
int a,b,m,pom;
for(a=0; a<pocet-1; a++){
pom = pole[a];
m = a;
for(b=a+1;b<pocet; b++)
if(pole[b] < pom){
m = b; /* min. prvok a index */
pom = pole[m];
};
pole[m] = pole[a];
pole[a] = pom; /* vymena */
};
}
void Shellsort(int pole[], int pocet)
/* triedenie vkladanim so zmensovanim kroku - Shell */
{
int a,b,m,k,presun,pom,t=4,h[]={1,2,4,8};
for(m=t-1; m>=0; m--){ /* kroky spracovania */
k = h[m];
do{
presun = 0; /* indikacia presunu */
for(a=k; a<pocet; a++){
pom = pole[a];
b = a-k;
if(pom<pole[b]){ /* porovnanie v kroku */
pole[a]=pole[b]; /* usporiad. v kroku */
pole[b]=pom;
presun = 1;
};
}
}while(presun>0);
}
}
void heapsort(int pole[], int pocet)
/* stromove triedenie - haldou */
{
int L,R,pom,*ppole;
void sift(int L, int R, int pole[]);
ppole=malloc(pocet+1); /* pom. pole */
for(L=0;L<pocet;L++)
ppole[L+1]=pole[L]; /* od 1 po pocet */
L=pocet/2+1; R=pocet;
while(L>1){ /* previerka prvkov */
L--;
sift(L,R,ppole);
};
while(R>1){
pom = ppole[1];
ppole[1]=ppole[R];
ppole[R]=pom;
R--;
sift(L,R,ppole);
};
for(L=0;L<pocet;L++) /* pole spat */
pole[L]=ppole[L+1];
free(ppole);
}
void sift(int L, int R, int pole[])
/* zaradenie prvku L do haldy */
{
int a,b,pom;
a=L; b=2*L;
pom = pole[L];
while(b<=R){
if(b<R)
if(pole[b]<pole[b+1]) b++;
if(pom >= pole[b])break;
pole[a]=pole[b];
a=b;
b=2*a;
}
pole[a]=pom;
/* getchar();
printf("\nS L %d R %d\n",L,R);
for(a=1;a<=16;a++)printf("%3d ",pole[a]);
*/
}
void quicksort(int pole[], int pocet)
/* triedenie rozdelovanim - rekurzivne */
{
void qs(int L, int R, int pole[]);
qs(0,pocet-1,pole);
}
void qs(int L, int R, int pole[])
/* vlastna funkcia triedenia v poli - Hoare */
{
int a,b,pom,pom1;
a=L; b=R; pom=pole[(L+R)/2]; /* vyber prvku */
do{
while((pole[a]<pom)&&(a<R)) a++;
while((pom<pole[b])&&(b>L)) b--;
if(a<=b){
pom1=pole[a];
pole[a]=pole[b];
pole[b]=pom1;
a++; b--;
}
}while(a<=b);
if(L<b)qs(L,b,pole);
if(a<R)qs(a,R,pole);
}
void mergesort(int pole[], int pocet)
/* triedenie metodou priameho zlucovania */
{
int i,j,k,L,t,h,m,p,q,r,up,*ppole;
ppole=malloc(2*pocet+1); /* pom. pole */
for(i=0;i<pocet;i++) /* indexy 1 az 2*pocet */
ppole[i+1]=pole[i]; /* od 1 po pocet */
up = p = 1;
do {
h = 1;
m = pocet;
if(up>0) { /* zdroj 1. cast */
i=1; j=pocet;
k=pocet+1; L=2*pocet;
}
else{ /* zdroj 2. cast */
k=1; L=pocet;
i=pocet+1; j=2*pocet;
};
/* zlucit postupnosti, urcene indexami i,j
do postupnosti urcenej indexom k;
q je dlzka i-postupnosti, r j-postupnosti */
do {
if(m>=p) q=p;
else q=m;
m=m-q;
if(m>=p) r=p;
else r=m;
m=m-r;
while((q!=0)&&(r!=0)){ /* zlucovanie */
if(ppole[i]<ppole[j]){
ppole[k]=ppole[i]; k=k+h;
i++; q--;
}
else{
ppole[k]=ppole[j]; k=k+h;
j--; r--;
};
}
while(r>0){ /* kopia zvysku j postupnosti */
ppole[k]=ppole[j]; k=k+h;
j--; r--;
};
while(q>0){ /* kopia zvysku i postupnosti */
ppole[k]=ppole[i]; k=k+h;
i++; q--;
};
h=-h; t=k;
k=L; L=t;
} while(m!=0);
up=-up; p=2*p;
} while(p<pocet);
if(up<0)
for(i=0;i<pocet;i++)
ppole[i]=ppole[i+pocet];
for(L=0;L<pocet;L++) /* pole spat */
pole[L]=ppole[L+1];
free(ppole);
}
int binsearch(int pole[], int pocet, int cislo)
/* binarne hladanie prvku cislo delenim intervalu
pole musi byt usporiadane - zotriedene !!! */
{
int a,b,pom;
a=0; b=pocet-1;
while(a<=b){
pom=(a+b)/2;
if(cislo<pole[pom])
b=pom-1;
else if(cislo>pole[pom])
a=pom+1;
else /* index prvku */
return pom;
}
return(-1); /* nenaslo sa */
}