Qsort (jazyk C)

Rozdelenie funkcií jazyka C podľa knižníc, v ktorých sú definované

<ctype.h>	<limits.h>	<stdio.h>	<stdlib.h>	<math.h>	<string.h>	<time.h>
isalnum isalpha isdigit isgraph islower isprint ispunct isspace isupper isxdigit		printf scanf getc putc getchar putchar fprintf fscanf fgetc fputc fopen fclose feof	system malloc qsort rand srand atoi atol atof itoa div abs labs	pow fabs exp log log10 sqrt ceil sin cos	strlen strcmp strchr strcpy strstr strcat strncat	clock time

Funkcia qsort

knižnica	stdlib.h
popis	Funkcia implementuje algoritmus vyhľadávania Quick sort.

Úplný funkčný prototyp funkcie qsort je nasledovný:

void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void *, const void *));

Ako vidíme funkcia má štyri parametre, ktorých význam je:

• base - ukazovateľ typu void ukazujúci na nultý element triedeného poľa
• nelem - počet elementov v triedenom poli
• width - veľkosť jedného elementu v bajtoch
• fcmp - ukazovateľ na porovnávaciu funkciu, ktorá porovnáva dva elementy triedeného poľa

Porovnávacia funkcia vyžaduje dva argumenty - ukazovatele typu const void *. Označme tieto argumenty elem1 a elem2. Potom úplný funkčný prototyp porovnávacej funkcie bude:

int (*fcmp)(const void *elem1, const void *elem2);

Od funkcie fcmp sa vyžaduje aby vracala celé číslo v závislosti od výsledku porovnania argumentov elem1 a elem2 nasledovne:

• ak *elem1 < *elem2 potom fcmp vráti celé číslo < 0
• ak *elem1 == *elem2 potom fcmp vráti 0
• ak *elem1 > *elem2 potom fcmp vráti celé číslo > 0

Pri porovnávaní elementov elem1 a elem2 symbol < znamená, že elem1 je menší ako elem2 v tom zmysle, že v utriedenom poli sa elem1 nachádza pred elem2. Podobne pre symbol >. Ak sú porovnávané elementy z pohľadu triediaceho kritéria ekvivalenté (symbol ==) potom funkcia vráti nulu. Napríklad ak porovnávame dva reťazce a kritériom je abcedné usporiadanie, potom reťazec "Alexandra" je menší ako reťazec "Zora". Ak by sme však chceli triediť podľa dĺžky reťazca, potom reťazec "Alexandra" je väčší ako reťazec "Zora".

Triedenie poľa sa potom realizuje volaním funkcie qsort s patričnými parametrami.

Poznámka: Pri porovnávaní porovnávame obsahy argumentov elem1 a elem2, to znamená, že píšeme napr. *elem1 < *elem2 namiesto elem1 < elem2. Zápis elem1 < elem2 by totiž znamenal, že máme porovnať hodnotu elem1 a elem2 čo by znamenalo, že máme porovnať nejaké adresy uložené v premenných elem1 a elem2 (tieto premenné sú ukazovatele a teda pamätajú adresu, nie samotnú štruktúru). Porovnanie elem1 < elem2 by teda bolo syntakticky správne, ale nemalo by zmysel. Chceme predsa porovnávať zamestnancov a nie adresy pamäte kde sú títo zamestnanci uložení.

Použitie funkcie qsort ilustrujeme na nasledujúcom jednoduchom príklade:

#include <stdio.h>
#include <stdlib.h>
#define POCET_PRVKOV 6

int pole[POCET_PRVKOV] = { 45, 11, 100, 30, 20, 27 };

int Porovnaj_cele_cisla (const void * a, const void * b)
{
   // Parameter "a" je ukazovateľ typu "const void *". Preto ho pred použitím musíme pretypovať na poiter na "int". Čiže: "(int *)a". 
   // Pretože zápis "(int *)a" predstavuje ukazovateľ a my chceme porovnávať celé číslo, ktoré je uložené tam kde tento ukazovateľ ukazuje
   // musíme ďalej napísať: "*(int *)a". Týmto zápisom sa dostaneme k hodnote čísla na ktoré ukazuje predaný parameter "const void * a".
   // Podobne pre parameter "b".
   return ( *(int*)a - *(int*)b );  
}

int main ()
{
  int n;
  // Vzostupné utriedenie poľa:
  qsort (pole, POCET_PRVKOV, sizeof(int), Porovnaj_cele_cisla);

  // Výpis na monitor:
  for (n=0; n<POCET_PRVKOV; n++)
     printf ("%d ",values[n]);
  return 0;
}