Algoritmy třídění

Naučit se programovat neznamená jen naučit se programovací jazyk, ale také vytvářet dobré programové algoritmy. Co si budeme nalhávat, jde hlavně o matematické algoritmy. S řešením všemožných záludných problému se programátor (nebo spíš analytik) setkává neustále. Není proto divu, že se najde spousta problémů, které už někdo řešil a vyřešil. Jedním z takových problémů je třídění. Na to, jak lze setřídit velké množství dat, se podíváte právě teď. Řešení algoritmů obecně není nijak závislé na programovacím jazyku, proto se při popisování programovacích jazyků s algoritmizací moc nesetkáte. Přesto je to mnohdy velice podstatná část návrhu programu a jeho optimalizace.

Funkce qsort()

Nejjednodušším řešením jak setřídit data v programovacím jazyku C je použití knihovní funkce qsort().

void  qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))

Pro zopakování ukážu jednoduchý příklad jejího použití. Její použití je efektivnější než použití následně probíraných algoritmů. Ty zde ukazuji jen jako příklad, abyste se nebáli převádět algoritmy do C. A také, abyste viděli, jak vám může pomoci mít rozhled nejen v syntaxi programovacího jazyka.

Vzhledem k tomu, že zde budu ukazovat třídění jednoduchého datového pole typu int, připomenu, jak by k třídění tohoto pole šlo použít funkce qsort().

Prvním argumentem funkce qsort() je „prázdný“ ukazatel na pole, které se bude třídit. Druhým argumentem je počet položek (rozměr) pole, třetím argumentem je velikost jedné položky (v příkladě je to počet bajtů typu int) a posledním argumentem je ukazatel na funkci (compar), podle které se budou porovnávat dva prvky z pole.

Tato porovnávací funkce musí mít dva parametry – ukazatele, kterými budou předány dvě hodnoty z pole na porovnání. Návratovou hodnotou této porovnávací funkce je typ int, podle kterého funkce qsort() pozná, který z porovnávaných prvků je větší. V případě, že větší je první prvek, musí vrátit porovnávací funkce kladnou hodnotu (1), pokud je menší vrátí hodnotu zápornou (-1) a pokud se rovnají, vrátí 0.
Tím „větší prvek“ myslím ten, který má být v setříděném poli dále než ten „menší“. Pokud návratové hodnoty v porovnávací funkci obrátíte, dojde k setřídění od největšího po nejmenší, ale to jsem snad ani nemusel dodávat :).

Nebudu tu psát celý příklad s výstupem, jen ukážu tu podstatnou část.

int pole[POLOZEK];

int vetsi(int *a, int *b)
{
    return *a - *b;
}

/* nezapomente nejdrive pole inicializovat nejakymi hodnotami */
qsort((void *) pole, POLOZEK, sizeof(pole[0]),
       (int (*)(const void *, const void *)) vetsi);

Buble sort

Algoritmus bublinkového třídění je poměrně jednoduchý ale ne moc efektivní. Procházíte několikrát celé pole (odzadu do předu) a porovnáváte sousední prvky. Pokud nejsou prvky správně seřazeny za sebou, prohodíte je. Takto nejmenší prvky „probublávají“ směrem k začátku (nebo to může být obráceně, chcete-li :-). Začínáte od konce pole a „probubláváte“ směrem na začátek. Po prvním průchodu máte zajištěno, že nejmenší prvek probublal na začátek pole a tak s ním v dalším cyklu už nemusíte počítat. Při pochopení tohoto algoritmu se soustřeďte nejdříve na pochopení jednoho kroku „probublávaní“, tj. jak vnitřní cyklus algoritmu prochází pole odzadu směrem dopředu a porovnává dva sousedící prvky pole.

  1. /*------------------------------------------------*/
  2. /* c41/bubble.c                                   */
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <time.h>
  7.  
  8. #define ROZMER 10
  9.  
  10. void vypis_pole(short int cykl, unsigned int pole[])
  11. {
  12.     unsigned short int i;
  13.     printf("Prvky pole (%2i):\n", cykl);
  14.  
  15.     /* schvalne, co by se stalo, kdyby byl ROZMER lichy ? */
  16.     for (i = 0; i < ROZMER / 2; i++)
  17.         printf("%2u: %u\t\t%2u: %u\n", i + 1, pole[i], i + ROZMER / 2 + 1,
  18.                pole[i + ROZMER / 2]);
  19.     /* spravna odpoved zni .... chvilka napeti ...
  20.      * posledni prvek z pole by se nevypsal.     */
  21. }
  22.  
  23. int main(void)
  24. {
  25.     size_t cykl, bublani;
  26.     unsigned int pole[ROZMER], pom;
  27.  
  28.     /* nejdrive inicializuji pole nahodnymi hodnotami a vypisi jej */
  29.     srand((unsigned int) time(NULL));
  30.  
  31.     for (cykl = 0; cykl < ROZMER; cykl++)
  32.         pole[cykl] = (rand() % 100) + 1;
  33.  
  34.     printf("Inicializace: \n");
  35.     vypis_pole(-1, pole);
  36.  
  37.     /* ted pole setridim algoritmem bubble sort */
  38.  
  39.     for (cykl = 1; cykl < ROZMER; cykl++) {
  40.         for (bublani = ROZMER - 1; bublani >= cykl; bublani--) {
  41.             printf(".");
  42.             if (pole[bublani - 1] > pole[bublani]) {
  43.                 /* mensi cislo probubla o jeden prvek smerem k zacatku */
  44.                 pom = pole[bublani - 1];
  45.                 pole[bublani - 1] = pole[bublani];
  46.                 pole[bublani] = pom;
  47.             }
  48.         }
  49.         /* vypise se mezivysledek, kde "cykl" nejmensich cisel
  50.          * uz je zarucene na zacatku pole */
  51.         printf("\n");
  52.         vypis_pole(cykl, pole);
  53.     }
  54.  
  55.     return 0;
  56. }
  57.  
  58. /*------------------------------------------------*/

Možný výstup z programu: 

Inicializace: 
Prvky pole (-1):                /* zde je inicializované a
 1: 26           6: 64             zatím nesetříděné, náhodně
 2: 87           7: 53             vygenerované pole */
 3: 81           8: 6
 4: 9            9: 23
 5: 17          10: 7
.........
Prvky pole ( 1):                /* po prvním "buble" cyklu nám
 1: 6            6: 17             probublalo na začátek
 2: 26           7: 64             nejmenší číslo 6.
 3: 87           8: 53             Všimněte si, že se nejdříve
 4: 81           9: 7              snažila probublat sedmička.  Ostatní
 5: 9           10: 23             čísla se jen posunuly o prvek níže. */
........
Prvky pole ( 2):
 1: 6            6: 9
 2: 7            7: 17
 3: 26           8: 64
 4: 87           9: 53
 5: 81          10: 23
.......
Prvky pole ( 3):
 1: 6            6: 81
 2: 7            7: 17
 3: 9            8: 23
 4: 26           9: 64
 5: 87          10: 53
......
Prvky pole ( 4):
 1: 6            6: 87
 2: 7            7: 81
 3: 9            8: 23
 4: 17           9: 53
 5: 26          10: 64
.....
Prvky pole ( 5):
 1: 6            6: 26
 2: 7            7: 87
 3: 9            8: 81
 4: 17           9: 53
 5: 23          10: 64
....
Prvky pole ( 6):
 1: 6            6: 26
 2: 7            7: 53
 3: 9            8: 87
 4: 17           9: 81
 5: 23          10: 64
...
Prvky pole ( 7):
 1: 6            6: 26
 2: 7            7: 53
 3: 9            8: 64
 4: 17           9: 87
 5: 23          10: 81
..
Prvky pole ( 8):           /* Pole je seřazeno, ale buble-sort
 1: 6            6: 26        o tom neví. Proto pokračuje ve třídění. */
 2: 7            7: 53
 3: 9            8: 64
 4: 17           9: 81
 5: 23          10: 87
.
Prvky pole ( 9):
 1: 6            6: 26
 2: 7            7: 53
 3: 9            8: 64
 4: 17           9: 81
 5: 23          10: 87

Tučně zvýrazněné jsou místa v poli, kde je zaručeno, že je pole seřazeno. (Proto se vnitřní průchozí cyklus 'for' zkracuje.)

Algoritmus bubble sort má pevně daný počet operací, který závisí jen na rozměru pole. I kdyby bylo pole už seřazeno, bubble-sort by provedl stejný počet operací. Tomu lze trochu pomoci tak, že se bude kontrolovat, zda se při „bubble“ cyklu nějaké prvky zaměnili. Pokud ne, algoritmus se ukončí. Tuto optimalizaci jistě zvládnete naprogramovat sami (máte to za domácí úkol ;-).

Quick sort

Algoritmus quick sort (nebo též „řazení dělením“) je jeden z nejefektivnějších. Princip je asi následující. Řazené pole se rozdělí na dvě části tak, aby v levé (první, horní říkejte tomu jak chcete …) části pole byly všechny čísla menší, než čísla v pravé části. Aby se to dobře programovalo, vezme se jeden prvek z pole (třeba prostřední, to je fuk), říkejme mu pivot a hledá se a třídí pole tak, že čísla z levé části jsou menší a čísla z pravé části jsou větší než pivot. Na oba úseky se použije rekurzivně stejný algoritmus, a tak se pole rozděluje na menší a menší úseky, až je rozdělené na úseky délky 1, čímž je pole setříděno.

Příklad:

  1. /*------------------------------------------------*/
  2. /* c41/quick.c                                    */
  3.  
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <time.h>
  7.  
  8. #define ROZMER 10
  9.  
  10. /**
  11. * funkce quicks se bude volat rekurzivne,
  12. * vzdy na levou a pravou cast
  13. */
  14. void vypis_usek(const unsigned int *pole, const char *text,
  15.                 const size_t zacatek, const size_t konec)
  16. {
  17.     size_t i;
  18.     printf("%-10s", text);
  19.     for (i = 0; i < ROZMER; i++) {
  20.         if (i < zacatek || i > konec) {
  21.             printf("-- ");
  22.         } else {
  23.             printf("%2u ", pole[i]);
  24.         }
  25.     }
  26.     printf("\n");
  27. }
  28.  
  29. void quicks(unsigned int *pole, const size_t levy_usek,
  30.             const size_t pravy_usek)
  31. {
  32.     size_t levy, pravy;
  33.     size_t pivot, pom;
  34.  
  35.     levy = levy_usek;
  36.     pravy = pravy_usek;
  37.  
  38.     pivot = pole[(levy + pravy) / 2];   /* vyber pivota zhruba u prostred */
  39.     printf("pivot: pole[%u] = %u\n", (levy + pravy) / 2, pivot);
  40.     vypis_usek(pole, "Pred:", levy_usek, pravy_usek);
  41.  
  42.     do {
  43.         while (pole[levy] < pivot)
  44.             levy++;
  45.         while (pivot < pole[pravy])
  46.             pravy--;
  47.  
  48.         if (levy <= pravy) {
  49.             pom = pole[levy];
  50.             pole[levy] = pole[pravy];
  51.             pole[pravy] = pom;
  52.             levy++;
  53.             pravy--;
  54.         }
  55.  
  56.     } while (levy <= pravy);
  57.  
  58.     vypis_usek(pole, "Po:", levy_usek, pravy_usek);
  59.     /* ted vime, ze vsechny cisla od "levy_usek" k "pravy"
  60.        jsou mensi nebo rovna cislum od "levy" po pravy_usek */
  61.     if (levy_usek < pravy)
  62.         quicks(pole, levy_usek, pravy); /* razeni leve casti */
  63.     if (levy < pravy_usek)
  64.         quicks(pole, levy, pravy_usek); /* razeni prave casti */
  65.  
  66. }
  67.  
  68. int main(void)
  69. {
  70.     size_t cykl;
  71.     unsigned int pole[] = { 74, 43, 94, 6, 89, 76, 88, 33, 52, 59 };
  72.  
  73.     printf("%-10s", "Start:");
  74.  
  75.     for (cykl = 0; cykl < ROZMER; cykl++) {
  76.         printf("%2u ", pole[cykl]);
  77.     }
  78.     printf("\n");
  79.  
  80.     /* ted se pole setridi algoritmem quick sort */
  81.     quicks(pole, 0, ROZMER - 1);
  82.  
  83.     printf("%-10s", "Konec:");
  84.     for (cykl = 0; cykl < ROZMER; cykl++) {
  85.         printf("%2u ", pole[cykl]);
  86.     }
  87.     printf("\n");
  88.  
  89.     return 0;
  90. }
  91.  
  92. /*------------------------------------------------*/

Pochopení tohoto algoritmu možná není nejsnazší. Ale věřte, že existují ještě „horší“ algoritmy na třídění, se kterými se můžete setkat ve zdrojových kódech. Ale teď už by vás snad něco takového nemělo rozházet. V knihkupectví určitě najdete nějaké knihy, které se zabývají právě algoritmizací úloh pro programování. Určitě není špatný nápad po nějaké šáhnout. Můžete si taky nastudovat skvělý web algoritmy.net.

A na závěr výstup z programu: 

Start:    74 43 94  6 89 76 88 33 52 59 
pivot: pole[4] = 89
Pred:     74 43 94  6 89 76 88 33 52 59 
Po:       74 43 59  6 52 76 88 33 89 94 
pivot: pole[3] = 6
Pred:     74 43 59  6 52 76 88 33 -- -- 
Po:        6 43 59 74 52 76 88 33 -- -- 
pivot: pole[4] = 52
Pred:     -- 43 59 74 52 76 88 33 -- -- 
Po:       -- 43 33 52 74 76 88 59 -- -- 
pivot: pole[2] = 33
Pred:     -- 43 33 52 -- -- -- -- -- -- 
Po:       -- 33 43 52 -- -- -- -- -- -- 
pivot: pole[2] = 43
Pred:     -- -- 43 52 -- -- -- -- -- -- 
Po:       -- -- 43 52 -- -- -- -- -- -- 
pivot: pole[5] = 76
Pred:     -- -- -- -- 74 76 88 59 -- -- 
Po:       -- -- -- -- 74 59 88 76 -- -- 
pivot: pole[4] = 74
Pred:     -- -- -- -- 74 59 -- -- -- -- 
Po:       -- -- -- -- 59 74 -- -- -- -- 
pivot: pole[6] = 88
Pred:     -- -- -- -- -- -- 88 76 -- -- 
Po:       -- -- -- -- -- -- 76 88 -- -- 
pivot: pole[8] = 89
Pred:     -- -- -- -- -- -- -- -- 89 94 
Po:       -- -- -- -- -- -- -- -- 89 94 
Konec:     6 33 43 52 59 74 76 88 89 94

A to je ode mne vše, přátelé!

Komentář Hlášení chyby
Created: 29.8.2003
Last updated: 27.6.2014
Tato stánka používá ke svému běhu cookies, díky kterým je možné monitorovat, co tu provádíte (ne že bych to bez cookies nezvládl). Také vás tu bude špehovat google analytics. Jestli si myslíte, že je to problém, vypněte si cookies ve vašem prohlížeči, nebo odejděte a už se nevracejte :-). Prohlížením tohoto webu souhlasíte s používáním cookies. Dozvědět se více..