V minulΘm dφlu jsme se zaΦali v∞novat algoritm∙m, kterΘ t°φdφ ·daje ulo₧enΘ v polφch. Dnes jich jeÜt∞ pßr p°idßme, abychom pak p°i programovßnφ reßln²ch aplikacφ m∞li z Φeho vybφrat. Doufßm, ₧e se Vßm dalÜφ pokraΦovßnφ bude lφbit.
Minule jsme probrali t°i algoritmy t°φd∞nφ, konkrΘtn∞:p°φm² v²b∞r, bublinkovΘ t°φd∞nφ a jeho modifikaci t°φd∞nφ p°et°ßsßnφm. Dnes si ukß₧eme metodu t°φd∞nφ pomocφ p°φmΘho vklßdßnφ. PotΘ p°ejdeme k slo₧it∞jÜφm algoritm∙m zalo₧en²m na rekurzi. Jsou to algoritmy znßmΘ pod jmΘny Quicksort a t°φd∞nφ sluΦovßnφm - Mergesort, kterΘ jsou zalo₧enΘ na rozd∞lovßnφ t°φd∞nΘho pole na ·seky.
Podobn∞ jako v p°φpad∞ algoritmu p°φmΘho v²b∞ru vznikß v levΘ Φßsti uspo°ßdanß posloupnost. Z pravΘho ·seku nynφ bereme Φφsla v po°adφ jak nßsledujφ. VybranΘ Φφslo v₧dy zat°φdφme na sprßvnΘ mφsto v levΘ Φßsti pole. Najdeme tedy mφsto pro tento prvek a pop°φpad∞ odsuneme zbytek ji₧ set°φd∞nΘ posloupnosti o jedno mφsto doprava. P°i hledßnφ sprßvnΘho mφsta budeme postupovat nßsledovn∞:vφme, ₧e posloupnost vlevo od prvku je ji₧ set°φd∞nß, staΦφ tedy porovnat prvek pro kter² hledßme mφsto s prvkem kter² le₧φ vlevo od n∞j. Pokud je hledan² prvek v∞tÜφ nebo roven, pak le₧φ na svΘm mφst∞ a m∙₧eme p°ejφt na nßsledujφcφ prvek. Pokud ne, pak prvky prohodφme a pokraΦujeme v porovnßvßnφ s dalÜφm lev²m prvkem, dokud nenajdeme sprßvnou pozici v poli, tedy dokud nenajdeme prvek, kter² je menÜφ ne₧li prvek pro kter² hledßme mφsto nebo dokud se nedostaneme na prvnφ mφsto v poli. Jedna z mo₧n²ch implementacφ:
void PrimeVkladani(int *pPole, unsigned int dwVel)
{
unsigned
int j; // pomocny index
int iPomocna; // pro vymenu prvku
for(unsigned int i = 1; i < dwVel; i++)
{
iPomocna = pPole[i]; // prvek ktery zatridujeme
j = i - 1;
while((j >= 0) && (iPomocna < pPole[j]))
{
pPole[j+1] = pPole[j];
// posuny
j--; // jdeme na dalsi prvek
}
pPole[j+1] = iPomocna; // spravna pozice pro zatridovany prvek
}
}
K≤d naleznete v sekci Downloads (projekt PrimeVkladani).
T°φd∞nφ metodou quicksort je zalo₧eno na tom, ₧e z pole vybereme jeden prvek (tzv. pivot) a potΘ uspo°ßdßme prvky tak, aby vlevo od zvolenΘho prvku le₧ela Φφsla menÜφ a vpravo pak Φφsla v∞tÜφ. Tyto v²m∞ny budeme provßd∞t nßsledujφcφm zp∙sobem: vyjdeme od prvnφho prvku v levΘ Φßsti pole a budeme hledat prvek takov², jeho₧ hodnota je v∞tÜφ ne₧ hodnota zvolenΘho prvku. Zßrove≥ budeme postupovat z pravΘ Φßsti a hledat prvek, kter² tam nepat°φ (tedy jeho hodnota je menÜφ ne₧li hodnota zvolenΘho prvku). Pak tyto dva prvky vym∞nφme. Za vybran² prvek budeme v₧dy vybφrat prvek, kter² le₧φ zhruba uprost°ed t°φd∞nΘho intervalu. Nynφ mßme uspo°ßdßny prvky tak, ₧e vlevo od zvolenΘho le₧φ Φφsla menÜφ a vpravo Φφsla v∞tÜφ. Dßle postupujeme tak, ₧e budeme pomocφ rekurzivnφho volßn t°φdit ·seky vlevo a vpravo od zvolenΘho prvku. Takto budeme postupovat, dokud se nedostaneme k ·sek∙m dΘlky 1, kterΘ jsou ji₧ ut°φd∞ny.
Nejprve si jeÜt∞ n∞co povφme o rekurzivnφm volßnφ. Rekurzivnφ volßnφ znamenß, ₧e funkce n∞kde ve svΘm t∞le zavolß znovu samu sebe (p°φmß rekurze) nebo zavolß jinou funkci, kterß pak zavolß funkci p∙vodnφ (nep°φmß rekurze). Ka₧dΘ volßnφ funkce znamenß jistΘ zpomalenφ, proto₧e je t°eba vytvo°it lokßlnφ prom∞nnΘ, ulo₧it nßvratovou adresu apod. To mß takΘ za nßsledek, ₧e p°i volßnφ rekurzivnφch funkcφ se m∙₧e, vzhledem ke koneΦnosti pam∞ti stßt, ₧e dojde k vyΦerpßnφ pam∞ti zßsobnφku. Proto je t°eba zajistit, aby rekurze nebyla nekoneΦnß a jejφ hloubka (poΦet vno°en²ch volßnφ) nebyla moc velikß. Po seznßmenφ se s datov²mi strukturami, kterΘ jsou rekurzivnφ (prvek obsahuje odkaz na dalÜφ prvek stejnΘho typu, nap°. stromy), uvidφme, ₧e pou₧itφm rekurze se n∞kterΘ operace velice zjednoduÜφ.
Jako klasick² krßtk² p°φklad na rekurzi se uvßdφ v²poΦet faktorißlu. Faktorißl celΘho kladnΘho Φφsla N je definovßn jako nßsledujφcφ souΦin:
N! = N * (N - 1) * (N - 2) * ... * 1
a
0! = 1
To nßs p°ivede na rekurzivnφ vztah pro v²poΦet faktorißlu:
N! = N * (N - 1)!
Program pro v²poΦet hodnoty faktorißlu:
#include <iostream.h>
int Fakt(unsigned int _dwN)
{
if(0 == _dwN)
{
return 1;
}
else
{
return _dwN * Fakt(_dwN-1);
}
}
int main(int argc, char* argv[])
{
unsigned int N;
cout << "Zadejte kladne cislo, jehoz faktorial chcete spocitat: ";
cin >> N;
cout << endl << "Faktorial je: " << Fakt(N)
<< endl;
char c;
cin >> c;
return 0;
}
K≤d naleznete v sekci Downloads (projekt Faktorial).
Algoritmus je opravdu jen ukßzkov², proto₧e mnohem lepÜφho v²sledku dosßhneme p°i pou₧itφ cyklu. Ji₧ p°i hodnot∞ N=13 p°esßhneme maximßlnφ rozsah prom∞nnΘ typu unsigned int.
Nynφ se op∞t vrßtφme k naÜemu t°φdicφmu algoritmu Quicksort. Nejprve pomocnß procedura:
void qsort(int *pPole, int dwLevy, int dwPravy)
{
int iPivot, iVymena;
// hodnota prvku zhruba uprostred a pomocna promenna na
vymeny
int i, j;
// pozor, nesmi byt unsigned, obcas potrebujeme i zaporne hodnoty
i = dwLevy;
j = dwPravy; // indexy
// zvoleni hodnoty pivotu - hodnota
zhruba z prostredka pole
iPivot = pPole[(dwLevy + dwPravy) / 2];
do {
// hledame prvek, ktery nepatri na levou stranu pole
// (tento prvek je tedy vetsi nezli hodnota iPivot)
while(pPole[i] < iPivot) { i++; }
// takovy prvek byl nalezen, nyni musime najit prvek, ktery nepatri do prave
casti
// (tento prvek je tedy mensi nezli hodnota iPivot)
while(pPole[j] > iPivot) { j--; }
// pokud jsme se nedostali do opacne casti pole, tedy pokud se indexy
neprekrizily, pak
// prvky prohodime
if(i <= j) {
// prohodime prvky
iVymena = pPole[i];
pPole[i] = pPole[j];
pPole[j] = iVymena;
// posuneme se na dalsi prvky
i++;
j--;
}
} while(i < j);
// cyklus konci, pokud doslo k prekrizeni indexu
// v dalsim kroku se pole rozdeli na dva useky, ktere setridime, pokud jsou
ovsem v poradku indexy
if(dwLevy < j)
qsort(pPole, dwLevy, j);
if(i < dwPravy)
qsort(pPole, i, dwPravy);
}
Vlastnφ t°φdicφ funkce jen zavolß pomocnou funkci pro celΘ pole:
void QuickSort(int *pPole, unsigned int dwVel)
{
qsort(pPole, 0, dwVel - 1);
}
K≤d naleznete v sekci Downloads (projekt QuickSort).
Tento algoritmus se takΘ n∞kdy naz²vß t°φd∞nφm rozd∞lovßnφm, ale Φast∞ji se o n∞m hovo°φ jako o Quicksortu.
Quicksort si m∙₧eme naprogramovat nebo m∙₧eme pou₧φt funkci qsort(), kterß implementuje tento algoritmus a je souΦßstφ knihovny jazyka C. Funkce je definovßna v souboru stdlib.h, kter² tedy musφme vlo₧it, hlaviΦka knihovnφ funkce qsort() vypadß nßsledovn∞:
void __cdecl qsort (void *pPole, size_t nPocet, size_t dwVelikost, int (__cdecl *Porovnani)(const void *, const void *));
Funkce tedy krom∞ ukazatele na prvnφ prvek t°φd∞nΘho ·seku, poΦtu polo₧ek a velikosti polo₧ky vy₧aduje funkci o dvou prom∞nn²ch, kterß zajistφ porovnßnφ dvou prvk∙. Tuto funkci musφme sami napsat, hlaviΦka vypadß nßsledovn∞:
int Porovnani(const void *prvni, const void *druhy);
Funkce porovnßnφ vracφ nßsledujφcφ hodnoty:
zßpornΘ, pokud prvek na kter² ukazuje prvni je menÜi ne₧ prvek na kter² ukazuje druhy
rovnΘ 0, pokud jsou stejnΘ
kladnΘ, je-li prvek na kter² ukazuje prvni v∞tÜφ ne₧ prvek na kter² ukazuje druhy
Implementace porovnßvacφ funkce pro nßÜ p°φpad pole slo₧enΘho z prvk∙ typu int:
int Porovnani(const void *prvni, const void *druhy)
// funkce pro porovnani se samozrejme
muze jmenovat libovolne
{
if(*((int *)prvni) < *((int *)(druhy)))
{
return -1;
}
if(*((int *)prvni) > *((int *)(druhy)))
{
return 1;
}
return 0; //
prvky jsou shodne
}
int main(int argc,
char* argv[])
{
srand((unsigned)time(NULL)); // abychom dostali pri kazdem
spusteni jina cisla
for(int i = 0; i < 3; i++)
{
cout << "Nesetrideno: " << endl;
NaplnPole(Pole, 20);
TiskPole(Pole, 20);
qsort(Pole, 20, sizeof(int), Porovnani);
// volani knihovni funkce qsort
cout << "Setrideno: " << endl;
TiskPole(Pole, 20);
}
char c;
cin >> c;
return 0;
}
K≤d naleznete v sekci Downloads (projekt QuickSort1).
Poznßmka k p°etypovßnφ: ukazatel na void p°etypujeme na ukazatel na int a potΘ chceme hodnotu ulo₧enou na tΘto adrese.
A¥ u₧ zavolßme naÜi vlastnφ funkci nebo knihovnφ funkci, v²sledkem bude pole uspo°ßdanΘ vzestupn∞ podle velikosti jednotliv²ch prvk∙. Pokud bychom cht∞li data ut°φdit sestupn∞, pak staΦφ v porovnßvacφ funkci zam∞nit znamΘnka.
Tento algoritmus je op∞t zalo₧en na rozd∞lenφ t°φd∞nΘho ·seku na dv∞ poloviny, potΘ je ka₧dß Φßst set°φd∞na podle velikosti prvk∙. T°φd∞nφ obou polovin je stejnß operace jen s jin²mi indexy a proto op∞t vyu₧ijeme rekurze. Toto d∞lenφ, podobn∞ jako u Quicksortu, probφhß dokud nemßme ·seky dΘlky 1, se kter²mi nemusφme nic d∞lat, proto₧e jsou ji₧ ut°φd∞nΘ. ┌seky se potΘ sluΦujφ dohromady tak, ₧e dva sluΦovanΘ ·seky prochßzφme pomocφ index∙ a zapisujeme v₧dy menÜφ Φφslo do v²slednΘ posloupnosti. Narozdφl od p°edchozφch algoritm∙ budeme u t°φd∞nφ sluΦovßnφm pot°ebovat pomocnΘ pole, do kterΘho se bude uklßdat v²slednß set°φd∞nß posloupnost. Implementace rekurzivn∞ volanΘ funkce:
void msort(int *pPole, int *pPomPole, unsigned int dwLevy,
unsigned int dwPravy)
{
unsigned int dwStred; // index prvku uprostred trideneho useku
unsigned int i, j, k; // pomocne indexy
dwStred = (dwLevy + dwPravy) / 2;
if(dwLevy < dwStred)
{
msort(pPole, pPomPole, dwLevy, dwStred);
// trideni leveho useku
}
if((dwStred + 1) < dwPravy)
{
msort(pPole, pPomPole, dwStred + 1, dwPravy);
// trideni praveho useku
}
// nyni budeme slucovat
i = dwLevy; // levy usek
j = dwStred + 1; // pravy usek
k = dwLevy; // index ve vyslednem poli
// sloucime setridene useky do pomocneho pole
while((i <= dwStred) && (j <= dwPravy))
{
if(pPole[i] <= pPole[j])
{
pPomPole[k] = pPole[i];
i++;
}
else
{
pPomPole[k] = pPole[j];
j++;
}
k++;
}
// dokopirujeme zbytek leveho useku
while(i <= dwStred)
{
pPomPole[k] = pPole[i];
i++;
k++;
}
// dokopirujeme zbytek praveho useku
while(j <= dwPravy)
{
pPomPole[k] = pPole[j];
j++;
k++;
}
// nyni preneseme setrideny usek z pomocneho pole zpet do puvodniho
for(k = dwLevy; k <= dwPravy; k++)
{
pPole[k] = pPomPole[k];
}
}
Vlastnφ t°φdicφ funkce alokuje pomocnΘ pole, kterΘ je stejn∞ velkΘ jako p∙vodnφ. Zavolß t°φdicφ rekurzivnφ funkci a p°ed skonΦenφm jeÜt∞ uvolnφ pomocnΘ pole:
void MergeSort(int *pPole,
unsigned int dwVel)
{
// vytvorime pomocne pole
int *pPomPole = new int[dwVel];
if(pPomPole)
{
// utridime ho
msort(pPole, pPomPole, 0, dwVel - 1);
// docasne pole smazeme
delete[] pPomPole;
}
}
K≤d naleznete v sekci Downloads (projekt Slucovani).
Nakonec jsem se rozhodl p°idat jeÜt∞ pßr zajφmav²ch t°φdicφch algoritm∙, v p°φÜtφm dφlu si jeÜt∞ jeden nebo dva p°idßme a zkontrolujeme si, jak jsou na tom jednotlivΘ algoritmy p°i t°φd∞nφ polφ r∙zn²ch velikostφ. Pokud jste se tedy t∞Üili na rychlostnφ testy, tak se omlouvßm, ale p°φÜt∞ urΦit∞ budou.
PřφÜtě nashledanou.