Trier des données en C.

Voir version :

Pas de dépendances

Télécharger :

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

int compint(const void* a,const void* b)
{
    int* pa=(int*)a;
    int* pb=(int*)b;
    int ea=*pa;
    int eb=*pb;
    return ea-eb;
}

int main()
{
    int nombres[5];
    int i;
    printf("Entrez 5 nombres\n");
    for(i=0;i<5;i++)
        scanf("%d",&nombres[i]);
    qsort(&(nombres[0]),5,sizeof(int),compint);
    printf("tri ok.\n");
    for(i=0;i<5;i++)
        printf("%d\n",nombres[i]);
    return 0;
}

Une des fonctions les plus puissantes du C standard, contenue dans stdlib : qsort.

qsort trie un ensemble d'éléments contigus en mémoire. (contigu = qui se suit en mémoire)
Il le fait tres vite : pour ceux qui s'y connaissent en complexité, celle ci est en Teta(n*log(base2)n)

--> sur des machines actuelles, capable de trier 10 millions d'éléments en qq secondes (moins d'une minute)

4 parametres :

- l'adresse de début du bloc a trier.
- le nombre d'éléments dans ce bloc
- la taille de chaque élément
- un pointeur de fonction vers un type   int X(const void*,const void*)

(ainsi la taille du tableau est de nombre d'élements*taille elements)

Pour les 3 premiers parametres, un foetus pourrait comprendre.
Le 4e est plus difficile à cerner : un pointeur de fonction, appelé par qsort.

En fait, a vous d'implémenter une fonction (que j'ai dans l'exemple appelée compint) qui, prenant 2 éléments donnés
renvoie un nombre négatif si b>a et positif si b<a
qsort appelle beaucoup votre fonction, pour savoir.

en parametre, il passe un pointeur sur l'élément. Ce pointeur est de type void* car vous pouvez aussi bien trier des int
que des double que des truc avec qsort...

La premiere chose a faire donc dans votre qsort, c'est de caster ces pointeurs en pointeurs du type que vous triez : ici,
je cast les void* en int* (je crée pour cela pa et pb)
Ensuite, il est conseillé de récupérer a partir de la, les éléments eux meme : je cree ainsi ea et eb a partir de pa et pb
De la, j'ai bien, concretement, mes 2 int a comparer
et la, la soustraction des 2 me permettra simplement de savoir lequel est plus grand....

AUTRES APPLICATIONS :

Certes, pour des int, vous vous dites qu'ils se compliquent la vie...
Mais qsort est tres général :

Imaginons que vous ayez :

struct Mec
{
char nom[50];
int age;
int taille;
};

struct Mec Tablemecs[10];

Et que vous vouliez trier ces gars, selon leur age --> qsort le fait... et pourtant, ça ne paraissait pas évident !

voila comment ça marche dans ce cas :

qsort(&(Tablemecs[0]),10,sizeof(struct mec),compmec);

int compint(const void* a,const void* b)
{
struct mec* pa=(struct mec*)a;
struct mec* pb=(struct mec*)b;
return (pa->age)-(pb->age);
}