qsort în C

#include <stdlib.h>
void qsort(void *baza, size_t numar, size_t marime,
           int (*compara)(const void *, const void *));

Ce face qsort

qsort nu știe ce tip au elementele. Îi dai începutul tabloului, numărul de elemente, mărimea unui element (sizeof v[0]) și o funcție care compară două elemente primite ca const void *.

Funcția de comparare întoarce un număr negativ dacă primul element trebuie să fie înainte, 0 dacă sunt echivalente și pozitiv dacă trebuie să fie după. În interiorul ei convertești pointerii la tipul real. Pentru numere, forma (a > b) - (a < b) evită depășirea care poate apărea la a - b.

Standardul nu spune ce algoritm folosește qsort și nu garantează că sortarea este stabilă: elementele egale își pot schimba ordinea între ele.

Parametri

Parametru	Descriere
baza	Pointer la primul element.
numar	Câte elemente are tabloul.
marime	Mărimea unui element în octeți.
compara	Funcția de comparare (vezi pointerii la funcții).

Ce returnează

Nimic (void); tabloul este sortat pe loc.

Exemple

Exemplul 1: Note sortate crescător

#include <stdio.h>
#include <stdlib.h>

static int compara_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void) {
    int note[] = {7, 10, 4, 9, 8, 10, 5};
    size_t n = sizeof note / sizeof note[0];
    qsort(note, n, sizeof note[0], compara_int);
    for (size_t i = 0; i < n; i++) {
        printf("%d ", note[i]);
    }
    printf("\n");
    return 0;
}

Rezultat

4 5 7 8 9 10 10

Exemplul 2: Structuri sortate după preț, descrescător

#include <stdio.h>
#include <stdlib.h>

struct produs {
    const char *nume;
    double pret;
};

static int dupa_pret_desc(const void *a, const void *b) {
    const struct produs *x = a;
    const struct produs *y = b;
    return (x->pret < y->pret) - (x->pret > y->pret);
}

int main(void) {
    struct produs cos[] = {{"pâine", 4.5}, {"cafea", 32.9}, {"lapte", 7.2}};
    qsort(cos, 3, sizeof cos[0], dupa_pret_desc);
    for (size_t i = 0; i < 3; i++) {
        printf("%6.2f lei  %s\n", cos[i].pret, cos[i].nume);
    }
    return 0;
}

Rezultat

 32.90 lei  cafea
  7.20 lei  lapte
  4.50 lei  pâine

Exemplul 3: Șiruri sortate cu strcmp

Tabloul conține pointeri (const char *), deci funcția primește pointeri la pointeri.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int compara_siruri(const void *a, const void *b) {
    return strcmp(*(const char *const *)a, *(const char *const *)b);
}

int main(void) {
    const char *orase[] = {"Iasi", "Arad", "Cluj", "Bacau"};
    qsort(orase, 4, sizeof orase[0], compara_siruri);
    for (size_t i = 0; i < 4; i++) {
        printf("%s\n", orase[i]);
    }
    return 0;
}

Rezultat

Arad
Bacau
Cluj
Iasi

Greșeli frecvente

• Scrii return x - y; pentru int: la valori mari (de exemplu INT_MIN și 1) scăderea depășește și ordinea iese greșită.
• La un tablou de șiruri convertești greșit: elementele sunt char *, deci argumentul este un char **, nu un char *.
• Dai sizeof pointerului în loc de mărimea elementului; folosește sizeof v[0].

Comenzi înrudite

• bsearch: Caută rapid un element într-un tablou sortat (căutare binară) și întoarce un pointer la el sau NULL.
• Pointeri la funcții: O variabilă care ține adresa unei funcții: o poți schimba, pune în tablouri sau trimite altor funcții (callback).
• void * (pointer generic): Un pointer care poate păstra adresa oricărui tip de date, dar care trebuie convertit la un tip concret înainte de folosire.
• strcmp și strncmp: Compară două șiruri caracter cu caracter și spune dacă sunt egale sau care vine primul.
• struct: Grupează mai multe valori de tipuri diferite într-un singur tip nou, de exemplu numele, vârsta și orașul unei persoane.