Pas de dépendances
#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); }