Rendezések implementálása, mérése

A feladat

Vizsgáljunk meg néhány egyszerű rendezési algoritmus hatékonyságát, empirikusan! Mivel a rendezések hatékonysága a) a rendezendő sorozat hosszától, és b) a rendezettség fokától függ, ezért a programban ezeket igyekezni kell figyelembe vennünk. A következőképpen teszünk:

1. bekérjük a rendezendő elemek számát;

2. (esetleg véletlenszám-generátor használatával) feltöltjük a rendezésre váró tömböt megfelelő számú elemmel;

3. az összes számunkra érdekes rendezés eljárását ugyanarra a kezdő sorozatra lefuttatjuk, miközben mérjük és kiírjuk a hatékonysági jellemzőket.

A rendezettségi fokot definiáljuk négyféleképpen: rendezett, majdnem rendezett (azaz csak töredék számú elem lehet rossz helyen), véletlenszerűen feltöltött, illetve fordítva rendezett.

Hatékonysági jellemzők:

• a rendezésre fordított idő,
• a tömbelemek hasonlításainak a száma,
• a tömbelemek mozgatásainak száma.

A vizsgálatban részt vevő rendezések:

• egyszerű cserés,
• minimumkiválasztásos,
• buborék,
• javított buborék,
• beillesztéses,
• javított beillesztéses.

Vissza a tartalomjegyzékhez

A megoldás

Meggondolnivalók a megoldás előtt

Mi legyen a rendezendő elemek típusa? Mivel az a két jellegzetes művelet (hasonlítás, mozgatás) időigénye az elemtípus hosszától egyenes arányosan függ, ezért a rendezések összevetése szempontjából a legegyszerűbb számtípus (Egész) is éppolyan sokatmondó, mint bármi más, esetleg összetettebb. A kapott abszolút idők a típustól függhetnek, de az arányok nem.

Mivel számos függvényre bontjuk a programot, érdemes megfontolni a paraméterezés mikéntjét! Több lehetőséget ismertünk meg, amelyek közül a legegyszerűbbet választjuk most: a program paraméterei legyenek globálisan deklaráltak, ami lehetővé teszi, hogy a függvények tényleges paraméterátadási „szertartás” nélkül elérhessék őket.

Hogyan töltsük föl a rendezendő tömböt? Növekvően, illetve csökkenően feltölteni a tömböt gyerekjáték. Javasolhatók például az alábbi algoritmusok.

Növekedve feltöltés	Csökkenve feltöltés

A véletlenszerűen feltöltött is –mint látható– pofonegyszerű algoritmusú. A legbonyodalmasabb a „majdnem rendezett” algoritmusa. Két lépésből áll: 1) rendezetten feltöltjük, majd 2) néhány (mondjuk 10%-nyi) elemet a „jó helyéről” kimozgatunk. Lássuk egy lehetséges megoldás algoritmusát.

Véletlenszerűen feltöltés	Majdnem rendezve feltöltés

Véletlen számok generálása C++ nyelvben: egyetlen formulát kell csak felidéznünk az előadásból.

rand() % (b-a+1) + a

Hogyan biztosítható, hogy a véletlen számok segítségével feltöltött tömb ugyanaz legyen az összes rendezés számára? Miután föltöltöttük a rendezendő r tömböt, az első rendezés az eredeti sorrendet „elrontja” (hiszen épp ez a célja!). Ahhoz, hogy a következő rendező algoritmus is az eredetin mutassa be képességeit, készítenünk kell egy másolatot a tömbről egy s segéd tömbben.

A C++ nyelv nyújtotta lehetőségek az időmérésre: a clock() függvény egy egész szám formájában adja vissza a program indulása óta „eltelt” processzoridőt. E függvény használatához „inkludálnunk” kell a <time.h> headerfájlt is.

(Ha ezt másodpercben szeretnénk kifejezni, akkor a

clock()/CLOCKS_PER_SEC

formulával kell számolnunk.)

A keretprogram

Azért, hogy ne kelljen sok időt fordítani a gépelésre, az alábbi keretprogramot adjuk közre. Ebben a kitöltendő részeket egy kommentárral jelöltük ki:

/*Ide jön az r rendezése*/

Lássuk a némi magyarázattal fűszerezett keretprogramot!

A szokásos „köteles” kommenteket most is mellőztük. Az „újdonság” a time.h headerfájl, amely nemcsak a clock() függvénynek, hanem a véletlenszám-generáláshoz is szükséges, ui. a time() függvény segítségével fogjuk inicializálni a generátort:

#include <iostream>
#include <time.h>     //a time és clock függvényekhez
#include <stdio.h>    //a printf függvényhez
#include <windows.h>  //a srand függvényhez, a HANDLE típushoz, a system-hez (pause és a cls DOS-parancsokhoz)
using namespace std;

A globális deklarációk következnek. A kiN szorul csak némi magyarázatra. A futás közben a tömböt ki fogjuk listázni a képernyőre, hogy ellenőrizhessük a rendezettséget. Viszont annak érdekében, hogy „emészthető” mennyiségben kapjuk e számsorozatot, a kiN-nel korlátozzuk a kiírandó elemek számát. Nyilván addig jelenthet előnyt ez a lista, amíg a rendezési algoritmusaink szemantikáját ellenőrizzük. Ekkor viszont az elemszámnak nem is célszerű túlon túl nagynak lennie.

const int maxN=8001;//a sorozat maximális hossza
const int kiN=120;//a megjelenítendő (rész)sorozat hossza
int s[maxN],r[maxN];//segéd és rendezendő elemek tömbje
int elemSzam;//tényleges elemszám
int kezdet,veg,elteltIdo;//futási idő kezdete, vége, hossza
int hSzam, mSzam;//hasonlítások száma, mozgatások szám

A függvényprototípusok (szignatúrák) következnek:

//beolvassa a min..max közötti egész számot (max<min => max=végtelen)
void be_int(string kerdes, int &n, int min, int max, string uzenet);
//feltöltésmód beolvasása:
int feltoltesMod();
//feltöltő eljárások:
void feltoltVeletlennel();
void feltoltNovekedve();
void feltoltCsokkenve();
void feltoltMajdnemRendezve();
//hatékonyságméréshez:
void oraIndul();
void oraAll();
//r-et rendező eljárások:
void egyszeruCseres();
void minimumKivalsztasos();
void buborek();
void javitottBuborek();
void beilleszteses();
void javitottBeilleszteses();
//cout<=r[1..min(kiN,elemSzam)]
void tombKiiras(string cim);
void kiertekeles(string cim);
//r<=s:
void masol();
//billentyű-lenyomásra várakozik
void billreVar();
//kurzor-pozícionálás a konzol-ablakban:
void curPos(int s, int o);
//képernyőtörlés:
void ujLap();

A főprogram következik. Mint látható lesz: a feltöltés különböző módszereit tartalmazza ugyan a program, de közülük most mi, a program írói választjuk ki azt az egyet, amely szerint végezzük a vizsgálatot. Érdemes ezen majd túllépni, és rábízni a döntést a program használójára!

int main()
{
    srand(time(NULL));//véletlenszám-generátor inicializálása
    //a rendezendő tömb feltöltése:
    be_int("Elemszám:",elemSzam,11,maxN,"Nem jó elemszám!");
    switch (feltoltesMod())
    {
      case 0:
        feltoltNovekedve(); break;
      case 1:
        feltoltCsokkenve(); break;
      case 2:
        feltoltMajdnemRendezve(); break;
      case 3:
        feltoltVeletlennel(); break;
    }    //a rendezések:
    egyszeruCseres();
    minimumKivalasztasos();
    buborek();
    javitottBuborek();
    beilleszteses();
    javitottBeilleszteses();
    return 0;
}

A függvények definíciói jönnek. Először a jól ismert egész számot beolvasó, majd a feltöltési módot beolvasó függvény.

//beolvassa a min..max közötti egész számot (max<min => max=végtelen)
void be_int(string kerdes, int &n, int min, int max, string uzenet)
{
    bool hiba;
    string tmp;
    do
    {
      if (max>=min)
      {
        cout << kerdes << " (" << min << ".." << max << "):"; cin >> n;
        hiba=cin.fail() || n<min || n>max;
      }
        else
      {
        cout << kerdes << " (" << min << "..):"; cin >> n;
        hiba=cin.fail() || n<min;
      }
      if (hiba)
      {
        cout << uzenet << endl;
        cin.clear(); getline(cin,tmp,'\n');
      }
    }
    while(hiba);
}
//feltöltésmód beolvasása:
int feltoltesMod()
{
    int melyik;
    ujLap();
    cout << "Válasszon az a lábbi feltöltésmódok közül:" << endl;
    cout << "0: növekedően" << endl;
    cout << "1: csökkenve" << endl;
    cout << "2: majdnem (növekedően) rendezve" << endl;
    cout << "3: véletlenszerűen" << endl;
    do
    {
        curPos(9,9);
        cout << "Melyik (0..3): ";
        cin >> melyik;
    }
    while (0>melyik || melyik>3);
    return melyik;
}

A feltöltő függvények következnek. Annyit kell velük kapcsolatban észrevenni, hogy nem csupán az r tömböt állítják, hanem értelemszerűen a másolatként szolgáló s-et is.

void feltoltNovekedve()
{
    s[1]=rand()%elemSzam+1;
    r[1]=s[1];
    for(int i=2;i<=elemSzam;++i)
    {
        s[i]=s[i-1]+rand()%3;
        r[i]=s[i];
    }
    tombKiiras("Feltölt növekedve");
}
void feltoltCsokkenve()
{
    s[1]=rand()%elemSzam+1;
    r[1]=s[1];
    for(int i=2;i<=elemSzam;++i)
    {
        s[i]=s[i-1]-rand()%3;
        r[i]=s[i];
    }
    tombKiiras("Feltölt csökkenve");
}
void feltoltMajdnemRendezve()
{
    int j,k,sv;
    s[1]=rand()%elemSzam+1;
    r[1]=s[1];
    for(int i=2;i<=elemSzam;++i)
    {
        s[i]=s[i-1]+rand()%3;
        r[i]=s[i];
    }
    for(int i=1;i<=elemSzam/10;++i)
    {
        j=rand()%elemSzam+1;
        do
        {
            k=rand()%elemSzam+1;
        }
        while (j==k);
        sv=s[j]; s[j]=s[k]; s[k]=sv;
        r[j]=r[k]; r[k]=sv;
    }
    tombKiiras("Feltölt majdnem rendezve");
}
void feltoltVeletlennel()
{
    for(int i=1;i<=elemSzam;++i)
    {
        s[i]=rand()%elemSzam+1;
        r[i]=s[i];
    }
    tombKiiras("Feltölt véletlennel");
}

A hatékonyságmérés két központi függvénye jön. Az „óraállításon” felül a hasonlítás és a mozgatás számlálókat is alaphelyzetbe hozzák.

void oraIndul()
{
    kezdet=clock();
    hSzam=0; mSzam=0;
}
void oraAll()
{
    veg=clock();
    elteltIdo=veg-kezdet;
}

A megjelenítő eljárásban az igényes táblázatolás kedvéért felhasználjuk a C++ C-ből származó formázott kiíró műveleteit, és az ujLap-ban a konzolt törlő, az operációs rendszertől kölcsönvett cls parancsot.

void tombKiiras(string cim)
{
    ujLap();
    cout << cim << endl << endl;
    int meddig; //ameddig listázza az elemeket... az ellenőrzés kedvéért
    if (elemSzam<kiN)
    {
        meddig=elemSzam;
    }
    else
    {
        meddig=kiN;
    }
    for(int i=1;i<=meddig;++i)
    {
        printf("%4d",i); printf(":%5d",r[i]);
    }
    cout << endl;
    billreVar();
}
void kiertekeles(string cim)
{
    tombKiiras(cim);
    cout << "\nEltelt ido:" << elteltIdo;
    cout << " | Hasonlítások száma:" << hSzam <<
            " | Mozgatások száma:" << mSzam << endl;
    billreVar();
}

Az alábbiakban a hatékonyságméréssel kapcsolatot nyitó és záró tevékenységgel kibővített rendező függvények definícióit találjuk. A rendezést ide kell beillesztenünk.

void egyszeruCseres()
{
    oraIndul();
/*Ide jön az r rendezése*/
    oraAll();
    kiertekeles("Egyszerű cserés");
    masol(); /* Az eredeti érték visszaállítása*/
}
void minimumKivalasztasos()
{
    oraIndul();
/*Ide jön az r rendezése*/
     oraAll();
     kiertekeles("Minimumkiválasztásos");
     masol(); /* Az eredeti érték visszaállítása*/
}
void buborek()
{
    oraIndul();
/*Ide jön az r rendezése*/
    oraAll();
    kiertekeles("Buborékos");
    masol(); /* Az eredeti érték visszaállítása*/
}
void javitottBuborek()
{
    oraIndul();
/*Ide jön az r rendezése*/
    oraAll();
    kiertekeles("Javított buborékos");
    masol(); /* Az eredeti érték visszaállítása*/
}
void beilleszteses()
{
    oraIndul();
/*Ide jön az r rendezése*/
    oraAll();
    kiertekeles("Beillesztéses");
    masol(); /* Az eredeti érték visszaállítása*/
}
void javitottBeilleszteses()
{
    oraIndul();
 /*Ide jön az r rendezése*/
    oraAll();
    kiertekeles("Javított beillesztéses");
    masol(); /* Az eredeti érték visszaállítása*/
}

S végül néhány segédfüggvény definíciója zárja a programot.

//r<=s:
void masol()
{
    for (int i=1;i<=elemSzam;++i)
    {
        r[i]=s[i];
    }
}
//billentyű-lenyomásra várakozik
void billreVar()
{
    system("pause");//windows esetében!
}
//kurzor-pozícionálás a konzol-ablakban:
void curPos(int s, int o)
{
    HANDLE hkonzol;
    COORD hova;
    hova.X=o; hova.Y=s;
    SetConsoleCursorPosition (hkonzol,hova);
}
//képernyőtörlés:
void ujLap()
{
    system("cls"); //képernyőtörlés
}

A rendező függvények – a megoldás

A lényegi függvények megoldását alább mellékeljük. Ne felejtse a hSzam, mSzam számlálókat a megfelelő helyen a megfelelő értékkel növelni!

void egyszeruCseres()
{
    oraIndul();
    int i,j,sv,n=elemSzam;
    for (i=1;i<=n-1;++i)
    {
        for (j=i+1;j<=n;++j)
        {
            if (r[i]>r[j])
            {
                ++hSzam;
                sv=r[i]; r[i]=r[j]; r[j]=sv;
                mSzam+=3;
            }
        }
    }
    oraAll();
    kiertekeles("Egyszerű cserés");
    masol(); /* Az eredeti érték visszaállítása */
}
void minimumkivalasztasos()
{
    oraIndul();
    int i,j,sv,minind,n=elemSzam;
    for (i=1;i<=n-1;++i)
    {
        minind=i;
        for (j=i+1;j<=n;++j)
        {
            if (r[j]<r[minind])
            {
                ++hSzam;
                minind=j;
            }
        }
        sv=r[minind]; r[minind]=r[i]; r[i]=sv;
        mSzam+=3;
     }
     oraAll();
     kiertekeles("Minimumkiválasztásos");
     masol(); /* Az eredeti érték visszaállítása */
}
void buborek()
{
    oraIndul();
    int i,j,sv,n=elemSzam;
    for(i=n;i>=2;--i)
    {
        for( j=1;j<=i-1;++j)
        {
            if(r[j]>r[j+1])
            {
                ++hSzam;
                sv=r[j]; r[j]=r[j+1]; r[j+1]=sv;
                mSzam+=3;
            }
        }
    }
    oraAll();
    kiertekeles("Buborékos");
    masol(); /* Az eredeti érték visszaállítása */
}
void javitottBuborek()
{
    oraIndul();
    int cs,i,j,sv,n=elemSzam;
    i=n;
    while (i>=2)
    {
        cs=0;
        for(j=1;j<=i-1;++j)
        {
            if (r[j]>r[j+1])
            {
                ++hSzam;
                sv=r[j]; r[j]=r[j+1]; r[j+1]=sv;
                cs=j;
                mSzam+=3;
            }
        }
        i=cs;
    }
    oraAll();
    kiertekeles("Javított buborékos");
    masol(); /* Az eredeti érték visszaállítása */
}
void beilleszteses()
{
    oraIndul();
    int i,j,sv,n=elemSzam;
    for (i=2;i<=n;++i)
    {
        j=i-1;
        while((j>0) && (r[j]>r[j+1]))
        {
            ++hSzam;
            sv=r[j]; r[j]=r[j+1]; r[j+1]=sv;
            --j;
            mSzam+=3;
        }
    }
    oraAll();
    kiertekeles("Beillesztéses");
    masol(); /* Az eredeti érték visszaállítása */
}
void javitottBeilleszteses()
{
    oraIndul();
    int i,j,sv,n=elemSzam;
    for (i=2;i<=n;i++)
    {
        j=i-1; sv=r[i];
        ++mSzam;
        while((j>0) && (r[j]>sv))
        {
            ++hSzam;
            r[j+1]=r[j];
            --j;
            ++mSzam;
        }
        r[j+1]=sv;
        ++mSzam;
    }
    oraAll();
    kiertekeles("Javított beillesztéses");
    masol(); /* Az eredeti érték visszaállítása */
}

A program „használatba vétele”

Vissza a tartalomjegyzékhez

Házi feladat

Vissza a tartalomjegyzékhez