Datové struktury a algoritmy (5.)

Dnes se budeme prozatím naposledy, jak bylo slíbeno v posledním dílu, zabývat třídicími algoritmy - povíme si něco o stabilitě algoritmů a ukážeme si, jak této vlastnosti využít. Následovat bude algoritmus pro vyhledávání v utříděném poli. A konečně se dostaneme k první odvozené datové struktuře - konkrétně to bude zásobník.

5.1. Vlastnosti třídicích algoritmů - pokračování

Stabilita algoritmu určuje, jak algoritmus zachází s tříděnými prvky, které mají stejnou velikost (hodnotu klíče podle kterého třídíme). Algoritmus nazveme stabilním pokud se v setříděném poli nacházejí prvky ve stejném pořadí jako v původním poli. Toho se dá využít např. následujícím způsobem. Představme si seznam lidí, u nichž si uchováváme jméno a rok narození. Pro vyhledávání lidí se nám bude hodit mít seznam setříděný podle jmen. Později se však můžeme rozhodnout, že potřebujeme pracovat s rokem narození a bude třeba vypsat seznam lidí podle roku narození. Samozřejmě budeme chtít zachovat abecední pořadí osob narozených ve stejném roce. Není nic snazšího, než-li použít stabilního třídicího algoritmu a setřídit jím pole podle věku. Ukážeme si tedy příklad na setřídění pole, které bude sestávat z instancí objektů CClovek. Pro setřídění podle jmen použijeme algoritmus rychlého třídění (Quicksort) a pro setřídění podle roku narození pak algoritmu přímého vkládání (Insertsort). Kód (některé části jsou vynechány):

#include <iostream>

using namespace std;

class CClovek
{
    bool operator<(CClovek _pravy)
    {
        bool bNavrat = false;

        if(strcmp(m_Jmeno, _pravy.VratJmeno()) < 0)
        {
            bNavrat = true;
        }

        return bNavrat;
    }

    bool operator>(CClovek _pravy)
    {
        bool bNavrat = false;

        if(strcmp(m_Jmeno, _pravy.VratJmeno()) > 0)
        {
            bNavrat = true;
        }

        return bNavrat;
    }

    bool operator==(CClovek _pravy)
    {
        bool bNavrat = false;

        if(strcmp(m_Jmeno, _pravy.VratJmeno()) == 0)
        {
            bNavrat = true;
        }

        return bNavrat;
    }

    void Vypis()
    {
        cout << m_Jmeno << ", " << m_Rocnik << endl;
    }
};

void qsort1(CClovek *pPole, int dwLevy, int dwPravy)
{
    // ...
}

void QuickSortJmeno(CClovek *pPole, unsigned int dwVel)
{
    qsort1(pPole, 0, dwVel - 1);
}

void qsort2(CClovek *pPole, int dwLevy, int dwPravy)
{
    // ...
}

void QuickSortVek(CClovek *pPole, unsigned int dwVel)
{
    qsort2(pPole, 0, dwVel - 1);
}

void PrimeVkladani(CClovek *pPole, unsigned int dwVel)
{
    // ...
}

void VypisPole(CClovek *pPole, unsigned int dwVel)
{
    for(int i = 0; i < dwVel; i++)
    {
        pPole[i].Vypis();
    }
}

static char* Jmena[] = {"Ofelie", "Honza", "Zlatek", "Lenka", "Zuzana", "Ondra", "Petr", "Petra", "Jana", "Ema", "Michal",         "Jiri", "Karel", "Zdenek", "Martin", "Lucie", "Tereza", "Martina", "Ivana", "Lukas" };

static unsigned short Roky[] = { 1980, 1980, 1950, 1982, 1981, 1982, 1977, 1983, 1999, 1955, 1980, 1980, 1981, 1955, 1974, 1984,     1980, 1982, 1911, 1980 };

int main(int argc, char* argv[])
{
    CClovek pole[20];

    for(int i = 0; i < 20; i++)
    {
        pole[i].NastavJmeno(Jmena[i]);
        pole[i].NastavRok(Roky[i]);
    }

    cout << "Podle roku narozeni pred setridenim podle jmen: " << endl;

    PrimeVkladani(pole, 20);

    VypisPole(pole, 20);

    cout << endl << "Setrideni podle jmena: " << endl;

    QuickSortJmeno(pole, 20);

    VypisPole(pole, 20);

    // Nyni mame seznam setriden podle jmen. Pokud ho nyni setridime stabilnim algoritmem podle roku narozeni, pak
    // budeme mit setridene lidi pod jednotlivymi daty opet podle jmena

    cout << endl << "Podle roku narozeni (stabilni algoritmus) po setrideni podle jmen: " << endl;

    PrimeVkladani(pole, 20);

    VypisPole(pole, 20);

    // nyni utridime pole opet podle jmena
    QuickSortJmeno(pole, 20);

    // a zkusime nestabilni algoritmus podle veku (QuickSortVek())
    cout << endl << "Podle roku narozeni (NEstabilni algoritmus) po setrideni podle jmen: " << endl;

    QuickSortVek(pole, 20);

    VypisPole(pole, 20);

    char c;
    cin >> c;

    return 0;
}

Pro třídu CClovek máme přetíženy operátory porovnání, takže porovnání dvou instancí této třídy znamená lexikografické porovnání jmen. Lexikografické porovnání je provedeno pomocí knihovní funkce strcmp(), ovšem pro češtinu bychom si museli napsat vlastní (např. kvůli ch). Dále máme dvě verze třídění pomocí algoritmu rychlého třídění, jedna utřídí pole podle jména a druhá podle věku. Procedura PrimeVkladani() implementuje příslušnou třídicí metodu. Poslední je pak pomocná procedura pro kontrolní výpis pole.

My si všimneme především dvou posledních výpisů. První výpis ukazuje stav po utřídění stabilním algoritmem - zůstalo nám zachováno abecední pořadí osob se stejným rokem narození (ale pole muselo být předtím setříděno podle abecedy). Poslední výpis pak ukazuje, co se stane pokud použijeme nestabilního algoritmu (Quicksort) - dojde k zpřeházení jmen.

Z algoritmů se kterými jsme se seznámili patří mezi stabilní:

Bublinka() - bublinkové třídění
Bublinka2() - bublinkové třídění s kontrolou prohození
Pretres() - třídění přetřásáním
PrimeVkladani() - třídění přímým vkládáním
MergeSort() - třídění slučováním. Pokud je ovšem implementováno jako nerekurzivní verze, pak je nestabilní
CountingSort() - třídění výpočtem pořadí

Mezi nestabilní pak patří:

PrimyVyber() - třídění přímým výběrem. Lze implementovat jako stabilní - z prvků se stejnými velikostmi se musí vybrat poslední
QuickSort() - rychlé třídění
ShellSort() - Shellovo třídění

5.2. Vyhledávání v setříděném poli

V druhém dílu seriálu věnovanému datovým strukturám a algoritmům jsme se seznámili s algoritmem pro vyhledání hodnoty v poli. Pole jsme museli ovšem celé, prvek po prvku, projít, protože se jednalo o nesetříděné pole. Nyní už víme jak pole utřídit a dokonce si můžeme vybrat z několika algoritmů. Následující algoritmus pro vyhledávání prvku v utříděném poli je vám všem určitě dobře znám, tedy pokud jste se alespoň jednou v životě setkali třeba s telefonním seznamem. Je jasné, že v telefonním seznamu se nedá hledat od začátku a postupovat jméno po jménu. Lepší je vzít seznam, otevřít ho zhruba v polovině, podívat se na jméno, to porovnat s hledaným jménem a podle výsledku porovnání se vrhnout na levou nebo pravou část. Takový algoritmus si právě naprogramujeme:

int Hledani(int *pPole, unsigned int dwVelikost, int iHodnota)
{
    int iIndex;    // navratova hodnota - index hledaneho prvku nebo -1 pokud je prvek nenalezen

    unsigned int dwLevy = 0, dwPravy = dwVelikost - 1;

    do {
        iIndex = (dwLevy + dwPravy) / 2;

        if(iHodnota > pPole[iIndex])
        {
            dwLevy = iIndex + 1; // neni v leve polovine pole
        }
        else
        {
            dwPravy = iIndex - 1; // neni v prave polovine pole
        }
    } while((iHodnota != pPole[iIndex]) && (dwLevy <= dwPravy)); // dokud neni prvek nalezen, nebo nedojde k prekrizeni indexu

    if(iHodnota != pPole[iIndex])
    {
        iIndex = -1; // hodnota se v poli nenachazi, smycka skoncila prekrizenim indexu
    }

    // jinak iIndex urcuje, kde se nachazi prvek

    return iIndex;
}

Algoritmy pro hledání v nesetříděném poli měly složitost O(n), tento algoritmus má složitost O(log n), což je pro rozsáhlá pole veliký rozdíl. Nesmíme však zapomenout, že pole musí být utříděné, jinak algoritmus nebude fungovat.

5.3. Datové struktury - zásobník

Dnes se seznámíme s první ze dvou datových struktur, které budeme implementovat pomocí polí. V některém z pozdějších dílů si ukážeme i implementaci založenou na lineárních spojových seznamech. Protože jsme dobře seznámeni s objektovým programováním v jazyce C++, budeme datové struktury implementovat v podobě tříd a využijeme i šablon.

5.3.1. Zásobník (stack)

Zásobník nám umožňuje přidávání a ubírání prvků pouze z jednoho konce pole (tomuto prvku říkáme vrchol zásobníku). Druhý konec se nazývá dnem zásobníku a není možné z tohoto konce odebírat nebo přidávat prvky (stejně jako to není možné z prostředku pole). Vybrání prvku ze zásobníku znamená tedy ubrání posledně přidaného prvku, proto se také zásobník označuje jako struktura typu LIFO (z angl. Last in, first out (poslední dovnitř, první ven)). Následuje rozhraní třídy a implementace metod:

// Hlavickovy soubor Zasobnik.h - deklarace tridy pro strukturu zasobnik

#ifndef ZASOBNIK_H
    #define ZASOBNIK_H

    #include <iostream.h>

    template<class T> class CZasobnik {
    private :
        T *m_Pole;
        int m_Velikost; // Velikost zasobniku
        int m_Vrchol; // kde se prave nachazi vrchol zasobniku

    public :
        CZasobnik(int _Velikost);
        ~CZasobnik();

        bool Vloz(const T& _Vklad);
        bool Vyjmi(T& _Vyber);

        bool JePrazdny() { return ((-1 == m_Vrchol) ? true : false); }
        bool JePlny() { return ((m_Velikost - 1) == m_Vrchol); }

        void Vypis();
    };

    template<class T> CZasobnik<T>::CZasobnik(int _Velikost)
    {
        m_Velikost = -1;
        m_Vrchol = -1;

        m_Pole = new T[_Velikost];

        if(m_Pole)
        {
            // pokud se podarilo nastavime velikost
            m_Velikost = _Velikost;
        }
    }

    template<class T> CZasobnik<T>::~CZasobnik()
    {
        if(m_Pole)
        {
            delete[] m_Pole;
            m_Pole = NULL;
            m_Velikost = 0;
        }
    }

    template<class T> bool CZasobnik<T>::Vloz(const T& _Vklad)
    {
        bool bNavrat = false;

        if(m_Pole)
        {
            if(!JePlny()) // pokud neni zasobnik plny
            {
                m_Vrchol++;

                m_Pole[m_Vrchol] = _Vklad;

                bNavrat = true;
            }
        }

        return bNavrat;
    }

    template<class T> bool CZasobnik<T>::Vyjmi(T& _Vyber)
    {
        bool bNavrat = false;

        if(m_Pole)
        {
            if(!JePrazdny())
            {
                _Vyber = m_Pole[m_Vrchol];

                m_Vrchol--;

                bNavrat = true;
            }
        }

        return bNavrat;
    }

    template <class T> void CZasobnik<T>::Vypis()
    {
        if(m_Pole)
        {
            if(!JePrazdny())
            {
                cout << "Obsahuje " << m_Vrchol + 1 << " objektu (volnych " << m_Velikost - (m_Vrchol + 1) << ")" << endl;
                for(int i = 0; i <= m_Vrchol; i++)
                {
                    cout << m_Pole[i] << endl;
                }
            }
            else
            {
                cout << "Seznam je prazdny" << endl;
            }
        }
    }

#endif

Jak jsme se dozvěděli v kurzu číslo 16 věnovanému jazyku C++, tak šablony vyžadují speciální postup při kompilaci a proto je šablona implementována přímo v hlavičkovém souboru.

Většinou se pro zásobník implementuje ještě metoda pro nakouknutí na prvek ležící na vrcholu zásobníku. Metoda je úplně stejná jako metoda Vyjmi(), ale uvnitř těla neměníme členskou proměnnou m_Vrchol. Metodu zde neuvádím, ale je implementována v přiloženém projektu jako metoda Nakoukni().

Protože datová struktura zásobník je velice důležitou a často používanou, uvedu si i anglické ekvivalenty jednotlivých metod:

Vloz() - PUSH
Vyjmi() - POP
Nakoukni() - PEEK

Pokud jste se někdy setkali s kódem napsaným v assembleru, pak první dvě z nich jsou instrukcemi procesoru řady x86 určené právě pro ukládání (resp. vybírání) údajů do/z datové struktury přístupné programu, což je právě náš zásobník. Používají se například při volání funkcí pro uložení parametrů, vytváření lokálních proměnných a také pro uložení adresy pro návrat z podprogramu. Pokud bude zájem, pak se v některém z dalších článků na základy assembleru podíváme.

5.4. Co bude příště

Seznámíme se s druhou strukturou založenou na polích - frontou. Probereme také její modifikace - oboustrannou frontu a kruhovou frontu. Pokračovat budeme lineárním spojovým seznamem a budeme pomocí něho implementovat zásobník a frontu.

Příště nashledanou.

Ondřej Burišin