Úvod
Novinky
Jazyk C/C++
PostgreSQL
Python
Linux
Windows
Psaní deseti prsty
Školní projekty
Programy
Vývoj PC
Autor
Kontakt
Odkazy
Lauřin deníček
2009-11-15
| ← spouštění programů | C/C++ |
Algoritmy třídění
Naučit se programovat neznamená jen naučit se programovací jazyk, ale také vytvářet dobré programovací 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í. Jak lze setřídit velké množství dat se podíváme 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 toho, jak dobré je mít rozhled nejen v programovacím jazyku.
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. (Jelikož budeme třídit pole typu int, přetypujeme ukazatel na ukazatel na typ int.) Druhým argumentem je počet položek (rozměr) pole, třetím argumentem je velikost jedné položky (v našem případě 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 argumenty – 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 sem snad ani
nemusel dodávat :).
Nebudu tu psát celý příklad s výstupem, jen ukážu tu podstatnou část.
1: int pole[POLOZEK]; 3: int vetsi(int *a, int *b) 4: { 5: return *a - *b; 6: } 8: /* nezapomente nejdrive pole inicializovat nejakymi hodnotami */ 9: qsort((void *) pole, POLOZEK, sizeof(pole[0]), 10: (int (*)(const void *, const void *)) vetsi);
Buble sort
Algoritmus bublinkového třídění je poměrně jednoduchý ale ne moc efektivní. Procházíme několikrát celé pole (odzadu do předu) a porovnáváme sousední prvky. Pokud nejsou prvky správně seřazeny za sebou, prohodíme je. Takto nejmenší prvky „probublávají“ směrem k začátku (nebo to může být obráceně, chcete-li :-). Začínáme od konce pole a „probubláváme“ směrem na začátek. Po prvním průchodu máme zajištěno, že nejmenší prvek probublal na začátek pole a tak s ním v dalším cyklu už nemusíme 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: /* bubble.c */ 4: #include <stdio.h> 5: #include <stdlib.h> 6: #include <time.h> 8: #define ROZMER 10 10: void vypis_pole(short int cykl, unsigned int pole[]) 11: { 12: unsigned short int i; 13: printf("Prvky pole (%2i):\n", cykl); 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: } 23: int main(void) 24: { 25: unsigned int cykl, bublani; 26: unsigned int pole[ROZMER], pom; 28: /* nejdrive inicializujeme pole nahodnymi hodnotami a vypiseme jej */ 29: srand((unsigned int) time(NULL)); 31: for (cykl = 0; cykl < ROZMER; cykl++) 32: pole[cykl] = (rand() % 100) + 1; 34: printf("Inicializace: \n"); 35: vypis_pole(-1, pole); 37: /* ted pole setridime algoritmem bubble sort */ 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: /* vypiseme mezivysledek, kde "cykl" nejmensich cisel 50: * uz mame zarucene na zacatku pole */ 51: printf("\n"); 52: vypis_pole(cykl, pole); 53: } 55: return 0; 56: } 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 jednoduše zabránit 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: /* quick.c */ 4: #include <stdio.h> 5: #include <stdlib.h> 6: #include <time.h> 8: #define ROZMER 10 10: /* funkci quicks budeme volat rekurzivne, 11: * vzdy na levou a pravou cast */ 13: void vypis_usek(const unsigned int *pole, const char *text, 14: const unsigned int zacatek, const unsigned int konec) 15: { 16: unsigned int i; 17: printf("%-10s", text); 18: for (i = 0; i < ROZMER; i++) { 19: if (i < zacatek || i > konec) { 20: printf("-- "); 21: } else { 22: printf("%2u ", pole[i]); 23: } 24: } 25: printf("\n"); 26: } 28: void quicks(unsigned int *pole, const unsigned int levy_usek, 29: const unsigned int pravy_usek) 30: { 31: unsigned int levy, pravy; 32: unsigned int pivot, pom; 34: levy = levy_usek; 35: pravy = pravy_usek; 37: pivot = pole[(levy + pravy) / 2]; /* vybereme pivota */ 38: printf("pivot: pole[%u] = %u\n", (levy + pravy) / 2, pivot); 39: vypis_usek(pole, "Pred:", levy_usek, pravy_usek); 41: do { 42: while (pole[levy] < pivot) 43: levy++; 44: while (pivot < pole[pravy]) 45: pravy--; 47: if (levy <= pravy) { 48: pom = pole[levy]; 49: pole[levy] = pole[pravy]; 50: pole[pravy] = pom; 51: levy++; 52: pravy--; 53: } 55: } while (levy <= pravy); 57: vypis_usek(pole, "Po:", levy_usek, pravy_usek); 58: /* ted vime, ze vsechny cisla od "levy_usek" k "pravy" 59: jsou mensi nebo rovna cislum od "levy" po pravy_usek */ 60: if (levy_usek < pravy) 61: quicks(pole, levy_usek, pravy); /* razeni leve casti */ 62: if (levy < pravy_usek) 63: quicks(pole, levy, pravy_usek); /* razeni prave casti */ 65: } 67: int main(void) 68: { 69: unsigned int cykl; 70: unsigned int pole[] = { 74, 43, 94, 6, 89, 76, 88, 33, 52, 59 }; 72: printf("%-10s", "Start:"); 74: for (cykl = 0; cykl < ROZMER; cykl++) { 75: printf("%2u ", pole[cykl]); 76: } 77: printf("\n"); 79: /* ted pole setridime algoritmem quick sort */ 80: quicks(pole, 0, ROZMER - 1); 82: printf("%-10s", "Konec:"); 83: for (cykl = 0; cykl < ROZMER; cykl++) { 84: printf("%2u ", pole[cykl]); 85: } 86: printf("\n"); 88: return 0; 89: } 91: /*------------------------------------------------*/
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.
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
| ← spouštění programů | C/C++ |