Me voici enfin dans la bonne rubrique
Avant de comparer les 2 éléments entre eux et ce jusqu'au séparateur, je comprend :
void qsort(int arr[],int lidx,int ridx)
{
int mid,e,buffer;//mid=séparateur,e=index de repérage du séparateur
if(lidx>=ridx) //si au moins 2 éléments...
return;
mid=(lidx+ridx)/2; //ici, on calcule ou le séparateur va se trouver...
//On permutte le contenu du séparateur avec celui du 1er élément de manière à ne pas etre gêné avec le séparateur qui serait en plein milieu du tableau...
buffer=arr[mid];
arr[mid]=arr[lidx];
arr[lidx]=buffer;
e=lidx;//on copie l'index du 1er élément dans e
for(int k=lidx+1;k<=ridx;k++)//Pour une recherche allant de l'index 1 à la fin du tableau à trier
if(arr[k]<arr[lidx])//Si l'élément suivant est inférieur au précédent...
{
e++; //ici on incrémente l'index ou le séparateur se situe (afin de le retrouver plus tard...)
//Puis permutation...
J'espère que j'ai au moins bon dans mes commentaires...
Puis c'est pour la fameuse permutation qu'il y a un truc vraiment bizzare ! Si on prendre un tableau de 5 éléments (7,1,2,10,9) par exemple et que l'on simule le programme dès son lancement, voici ce que je comprends :
Après ça :
buffer=arr[mid];
arr[mid]=arr[lidx];
arr[lidx]=buffer;
On obtient ça du tableau :
(2,1,7,10,9)(du au placement en début de tableau du séparateur)
Début de simulation...1ère passe du for... k=lidx+1=0+1=1
lidx=0...
for(int k=lidx+1;k<=ridx;k++)
if(arr[k]<arr[lidx]) //si arr[1] (valeur :1)<arr[0] (valeur :2)
{
e++;
buffer=arr[e];//on met arr[1] dans le buffer (puisque e=1)
arr[e]=arr[k];//on met dans arr[1] arr[1] !!! j'en vois donc pas l'intérêt !
arr[k]=buffer;//et on met le contenu du buffer(arr[1]) dans arr[1] ???
}
Si quelqu'1 peut m'éclairer, ça serait bien gentil
car je vois vraiment pas ou est mon erreur de compréhension...(le prog est bon, il vient d'un livre...)
voici quand meme la fin du prog :
buffer=arr[e];
arr[e]=arr[lidx];
arr[lidx]=buffer;
qsort(arr,lidx,e-1);//tri du sous tableau de gauche
qsort(arr,e+1,ridx);//tri du sous tableau de droite
}
Message édité par neo9205 le 02-09-2003 à 19:37:37