Usare qsort
L'ordinamento della libreria standard
Usare qsort è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.
L'ordinamento della libreria standard
La libreria standard di C fornisce qsort in <stdlib.h>. Ordina qualsiasi array dato una funzione di confronto, quindi raramente è necessario scrivere un algoritmo di ordinamento personalizzato.
La firma di qsort
Il prototipo è:
basepuntatore al primo elementonmembnumero di elementisizenumero di byte per elementocomparpuntatore a una funzione di confronto
void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
Scrivere un comparatore
Il comparatore riceve due const void *. Li converta nel tipo effettivo, ne dereferenzi i puntatori e restituisca un valore negativo, zero o positivo.
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y); /* safe, no overflow */
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
qsort(a, 5, sizeof(int), cmp_int);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Eviti la sottrazione nei comparatori
Restituire x - y può causare un overflow per interi grandi, producendo risultati errati. Usi invece l'idioma della differenza tra valori booleani (x > y) - (x < y).
#include <stdio.h>
int main(void) {
int x = 2000000000, y = -2000000000;
printf("unsafe x-y = %d\n", x - y); /* overflow */
printf("safe = %d\n", (x > y) - (x < y));
return 0;
}Ordine decrescente
Per ordinare in senso decrescente, è sufficiente invertire il risultato del confronto.
#include <stdio.h>
#include <stdlib.h>
int cmp_desc(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (y > x) - (y < x);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
qsort(a, 5, sizeof(int), cmp_desc);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Ordinare stringhe
Per ordinare un array di char *, il comparatore riceve puntatori ai puntatori. Esegua il cast a const char * const * e chiami strcmp.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp_str(const void *a, const void *b) {
const char *x = *(const char * const *)a;
const char *y = *(const char * const *)b;
return strcmp(x, y);
}
int main(void) {
const char *names[] = {"charlie", "alice", "bob"};
qsort(names, 3, sizeof(char *), cmp_str);
for (int i = 0; i < 3; i++) printf("%s ", names[i]);
printf("\n");
return 0;
}Ordinare strutture
È possibile ordinare un array di strutture in base a qualsiasi campo. In questo esempio ordiniamo le persone in base all'età.
#include <stdio.h>
#include <stdlib.h>
typedef struct { char name[16]; int age; } Person;
int by_age(const void *a, const void *b) {
const Person *p = a, *q = b;
return (p->age > q->age) - (p->age < q->age);
}
int main(void) {
Person ppl[] = {{"Ann", 30}, {"Ben", 25}, {"Cid", 40}};
qsort(ppl, 3, sizeof(Person), by_age);
for (int i = 0; i < 3; i++) printf("%s %d\n", ppl[i].name, ppl[i].age);
return 0;
}Ordinamento per più chiavi
Per risolvere i pareggi, confronti un secondo campo quando il primo è uguale. In questo modo l'ordinamento avviene prima per età e poi alfabeticamente per nome.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct { char name[16]; int age; } Person;
int cmp(const void *a, const void *b) {
const Person *p = a, *q = b;
if (p->age != q->age)
return (p->age > q->age) - (p->age < q->age);
return strcmp(p->name, q->name);
}
int main(void) {
Person ppl[] = {{"Zoe", 30}, {"Amy", 30}, {"Bo", 25}};
qsort(ppl, 3, sizeof(Person), cmp);
for (int i = 0; i < 3; i++) printf("%d %s\n", ppl[i].age, ppl[i].name);
return 0;
}qsort non è stabile
Lo standard C non richiede che qsort sia stabile. Se ha bisogno della stabilità, aggiunga al comparatore una chiave per risolvere i pareggi, come l'indice originale.
Il complemento bsearch
bsearch esegue una ricerca binaria su un array ordinato usando lo stesso stile di comparatore. Lo abbini a qsort per ottenere ricerche rapide.
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a, y = *(const int *)b;
return (x > y) - (x < y);
}
int main(void) {
int a[] = {1, 3, 5, 7, 9};
int key = 7;
int *found = bsearch(&key, a, 5, sizeof(int), cmp_int);
printf("%s\n", found ? "found" : "missing");
return 0;
}Perché usare qsort
Il qsort standard è ampiamente testato, spesso è un ibrido introsort ottimizzato e funziona con qualsiasi tipo. Ricorra a un algoritmo personalizzato solo quando ha bisogno di stabilità o di un comportamento speciale che la libreria non può offrire.
Verifica rapida
Verifichi la propria comprensione di qsort.
Riepilogo
Ha imparato a usare l'ordinamento della libreria standard.
qsort(base, nmemb, size, compar)ordina qualsiasi array- I comparatori eseguono il cast di
const void *e restituiscono il segno del confronto - Eviti la sottrazione; usi
(x > y) - (x < y) qsortnon garantisce la stabilità;bsearchè il suo complemento per la ricerca
Domande Frequenti
La lezione «Usare qsort» è gratuita?
Sì — il testo completo di «Usare qsort» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.
Cosa imparerò in «Usare qsort»?
L'ordinamento della libreria standard Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare C Academy?
Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Usare qsort»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione C Academy?
Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.