0Pricing
C Academy · Leçon

Utiliser qsort

Le tri de la bibliothèque standard

Utiliser qsort est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.

Le tri de la bibliothèque standard

La bibliothèque standard de C fournit qsort dans <stdlib.h>. Il trie n’importe quel tableau à l’aide d’une fonction de comparaison, si bien que vous devez rarement écrire votre propre tri.

La signature de qsort

Le prototype est :

  • base pointeur vers le premier élément
  • nmemb nombre d’éléments
  • size nombre d’octets par élément
  • compar pointeur vers une fonction de comparaison

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

Écrire une fonction de comparaison

La fonction de comparaison reçoit deux const void *. Convertissez-les vers le type réel, déréférencez-les, puis renvoyez une valeur négative, nulle ou positive.

#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;
}

Éviter la soustraction dans les comparaisons

Renvoyer x - y peut provoquer un dépassement de capacité avec de grands entiers et produire des résultats incorrects. Utilisez plutôt l’idiome de différence de booléens (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;
}

Ordre décroissant

Pour trier dans l’ordre décroissant, inversez simplement le résultat de la comparaison.

#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;
}

Trier des chaînes

Pour trier un tableau de char *, la fonction de comparaison reçoit des pointeurs vers les pointeurs. Convertissez-les en const char * const *, puis appelez 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;
}

Trier des structures

Vous pouvez trier un tableau de structures selon n’importe quel champ. Ici, nous classons les personnes par âge.

#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;
}

Tri selon plusieurs clés

Pour départager les égalités, comparez un second champ lorsque le premier est égal. Le tri s’effectue ainsi d’abord par âge, puis par nom dans l’ordre alphabétique.

#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 n’est pas stable

La norme C n’exige pas que qsort soit stable. Si vous avez besoin de stabilité, ajoutez à votre fonction de comparaison une clé secondaire, comme l’index d’origine.

L’outil associé bsearch

bsearch effectue une recherche binaire dans un tableau trié en utilisant le même style de fonction de comparaison. Associez-le à qsort pour obtenir des recherches rapides.

#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;
}

Pourquoi utiliser qsort

Le qsort standard est largement testé, souvent fondé sur un hybride introspectif optimisé, et fonctionne avec n’importe quel type. N’écrivez votre propre tri que si vous avez besoin de stabilité ou d’un comportement particulier que la bibliothèque ne peut pas fournir.

Vérification rapide

Testez votre compréhension de qsort.

Récapitulatif

Vous avez appris à utiliser le tri de la bibliothèque standard.

  • qsort(base, nmemb, size, compar) trie n’importe quel tableau
  • Les fonctions de comparaison convertissent const void * et renvoient le signe du résultat de la comparaison
  • Évitez la soustraction ; utilisez (x > y) - (x < y)
  • qsort n’est pas garanti stable ; bsearch est l’outil de recherche associé

Questions Fréquemment Posées

La leçon « Utiliser qsort » est-elle gratuite ?

Oui — le texte complet de « Utiliser qsort » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Utiliser qsort » ?

Le tri de la bibliothèque standard Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer C Academy ?

Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Utiliser qsort » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon C Academy ?

Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Tri à bulles et par insertion
  2. Tri rapide
  3. Tri fusion
  4. Utiliser qsort
← Retour à C Academy