DatovΘ struktury a algoritmy (3.)

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.

3.1 DalÜφ t°φdicφ algoritmy

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.

3.1.1 P°φmΘ vklßdßnφ (Insert Sort)

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
    }
}

3.1.2 RychlΘ t°φd∞nφ (Quick Sort)

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

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;
}

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);
}

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;
}

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.

3.1.3 T°φd∞nφ sluΦovßnφm (Merge Sort)

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;
    }
}

3.2. Co bude p°φÜt∞

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.

Ond°ej BuriÜin