Třídění a vyhledávání
Třídění pole na základě porovnávání dvojic prvků je oblíbenou úlohou snad všech
učitelů informatiky,
neboť rozvíjí algoritmické myšlení studentů a umožňuje krátkou exkurzi
do teorie složitosti. Nejjednodušší algoritmy mají kvadratickou složitost,
lepší a složitější n * log(n). Jeden z těch
(v průměrném případě) velmi
rychlých se jmenuje quicksort a je implementovaný ve standardní knihovně
jazyka C.
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (* compar)(const void *, const void *));
Funkce qsort je navržena obecně, tak aby mohla třídit pole jakékoli velikosti a
typu prvků podle uživatelem definovaného uspořádání. Parametr base je ukazatel
na začátek pole, nmemb počet tříděných prvků a size velikost jednoho prvku
v bytech. Poslední parametr compar je ukazatel na porovnávací funkci
definovanou programátorem. Funkce musí vracet záporné, nulu nebo kladné číslo
pokud je první z dvojice porovnávaných prvků menší, rovný nebo větší než druhý.
Parametry třídící i porovnávací funkce jsou typu void *, při skutečném použití
bude třeba hojně přetypovávat. Ukážeme si to nejjednodušším na příkladu,
třídění náhodně vygenerovaných čísel typu unsigned int.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Velikost pole */
#define POCET 200
/* Porovnávací funkce, parametry jsou ukazatele na porovnávané prvky. */
int cmp(const void *a, const void *b) {
/* Parametry musíme nejprve přetypovat z void * na unsigned *, potom
dereferencovat na unsigned a teprve potom porovnat. */
if ( *((unsigned *) a) < *((unsigned *) b) ) {
/* První prvek je menší. */
return -1;
}
if ( *((unsigned *) a) > *((unsigned *) b) ) {
/* První prvek je větší. */
return 1;
}
/* Ani menší ani větší. V úplném uspořádání zbývá jedině rovnost. */
return 0;
}
int main(void) {
/* Tříděné pole */
unsigned pole[POCET];
int i;
/* Inicializace generátoru náhodných čísel */
srand(time(NULL));
/* Naplnění pole náhodnými čísly od nuly do 1000 */
for (i = 0; i < POCET; i++) {
pole[i] = rand() % 1000;
}
/* Výpis nesetříděného pole */
puts("Nesetříděno:");
for (i = 0; i < POCET; i++) {
printf("%u ", pole[i]);
}
/* Vlastní třídění */
qsort((void *) pole, POCET, sizeof(unsigned), cmp);
/* Výpis setříděného pole */
puts("\n\nSetříděno:");
for (i = 0; i < POCET; i++) {
printf("%u ", pole[i]);
}
/* Odřádkování na závěr */
puts("");
return 0;
}
V praxi se obvykle netřídí čísla ale záznamy podle nějakého klíče. Funkce qsort
je dostatečně obecná i pro tento případ. Ukážeme si, jak setřídit zaměstnance
firmy podle mzdy. Každý zaměstnanec má v našem příkladu jen jméno a plat,
ale ve skutečném případě by měl ještě další položky, například nějaké id,
adresu, rodné číslo, místo v kanceláři, nadřízeného atd. Bylo by možné
definovat přímo pole struktur Zamestnanec a třídit toto pole. Tato implementace
by ale byla poněkud neefektivní, neboť sizeof(Zamestnanec) není zanedbatelné
číslo a v průběhu třídění se budou prvky pole prohazovat, což by vedlo
k opakovanému kopírování větších bloků paměti. Lepší je definovat pole
ukazatelů na zaměstnance a třídit toto pole, neboť se budou prohazovat pouze
několikabytové ukazatele.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Velikost pole */
#define POCET 10
typedef struct {
unsigned plat;
char jmeno[64];
} Zamestnanec;
/* Porovnávací funkce, parametry jsou ukazatele na ukazatele na
porovnávané typy Zamestnanec. */
int cmp(const void *a, const void *b) {
/* Parametry musíme nejprve přetypovat z void * na Zamestnanec **, potom
dereferencovat na Zamestnanec *, operátorem -> získat mzdu a teprve
potom porovnat. */
if ( (*((Zamestnanec **) a))->plat <
(*((Zamestnanec **) b))->plat ) {
/* První prvek je menší. */
return -1;
}
if ( (*((Zamestnanec **) a))->plat >
(*((Zamestnanec **) b))->plat ) {
/* První prvek je větší. */
return 1;
}
/* Ani menší ani větší. V úplném uspořádání zbývá jedině rovnost. */
return 0;
}
int main(void) {
/* Tříděné pole */
Zamestnanec * pole[POCET];
int i;
/* Inicializace generátoru náhodných čísel */
srand(time(NULL));
/* Naplnění pole náhodnými zaměstnanci s platem od 10 do 60 tisíc */
for (i = 0; i < POCET; i++) {
Zamestnanec *pz;
pz = (Zamestnanec *) malloc(sizeof(Zamestnanec));
if (!pz) {
/* Ve skutečných programech takhle opatrný nejsem, ale tohle je
výuka... */
int j;
fputs("Málo paměti!\n", stderr);
for (j = 0; j < i; j++) {
free(pole[j]);
}
return 1;
}
pz->plat = 10000 + rand() % 50001;
sprintf(pz->jmeno, "Zaměstnanec%03i", i);
pole[i] = pz;
}
/* Výpis nesetříděného pole */
puts("Nesetříděno:");
for (i = 0; i < POCET; i++) {
printf("jméno: %s, plat:%u\n", pole[i]->jmeno, pole[i]->plat);
}
/* Vlastní třídění */
qsort((void *) pole, POCET, sizeof(Zamestnanec *), cmp);
/* Výpis setříděného pole */
puts("\n\nSetříděno:");
for (i = 0; i < POCET; i++) {
printf("jméno: %s, plat:%u\n", pole[i]->jmeno, pole[i]->plat);
}
/* Dealokace */
for (i = 0; i < POCET; i++) {
free(pole[i]);
}
/* Odřádkování na závěr */
puts("");
return 0;
}
Podobnou syntaxi jako qsort má i funkce bsearch, která hledá půlením intervalu
(tedy s logaritmickou časovou složitostí) v setříděném poli konkrétní
záznam.
#include <stdlib.h>
void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
int (* compar)(const void *, const void *));
Parametr key je něco jako kopie hledaného záznamu, přesně řečeno ukazatel,
jehož porovnání funkcí compar s hledaným záznamem vrací 0. V případě
zaměstnanců vyhledávaných a setříděných podle mzdy by se zřejmě jednalo
o ukazatel na strukturu Zamestnanec s vyplněnou položkou plat, na hodnotě
položky jmeno nezáleží. Funkce vrací ukazatel do pole na hledaný záznam nebo
NULL, pokud v poli není. Zbytek je stejný jako u funkce qsort. Na konec
minulého příkladu před cyklus s dealokací tak můžeme přidat následující kód:
{
Zamestnanec z, *pz, **ppz;
z.plat = 30000;
pz = &z;
/*
Návratová hodnota bsearch je ukazatel na prvek pole tedy ukazatel
na ukazatel na Zamestnanec. Musíme ji přetypovat z void *
na Zamestnanec **, ověřit, zda není NULL, dereferencí získat jednoduchý
ukazatel na Zamestnanec a teprve potom operátorem -> přistupovat
k položkám. Rovněž pozor na první vstupní parametr. Nejde zadat &z,
tedy Zamestnanec *. Je třeba stejný typ, jako je ukzatel na prvek pole,
tedy Zamestnanec **.
Práce s ukazateli dělá občas problémy i zkušeným programátorům v C.
*/
ppz = (Zamestnanec **) bsearch(&pz, pole, POCET, sizeof(Zamestnanec *),
cmp);
if (!ppz) {
printf("Plat přesně %u nemá nikdo.\n", z.plat);
} else {
printf("Plat přesně %u má %s a možná ještě někdo další.\n", z.plat,
(*ppz)->jmeno);
}
}
Všimněte si výpisu v případě úspěšného hledání. Náš příklad se trochu podobá
vyhledávání v databázi, ale narozdíl od příkazu SELECT v SQL může bsearch
i v případě duplicit vrátit pouze jedinou hodnotu.
Pokračování příště
Vyhledávání zaměstnanců nám dnešní díl poněkud roztáhlo, proto se ke slíbené
práci se znaky dostaneme až příště a povíme si i něco o ladícím makru assert.