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