Quick Sort fait une boucle infinie

delfre56 Messages postés 350 Date d'inscription   Statut Membre Dernière intervention   -  
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   -
Bonjour,
J'essaie d'écrire une fonction utilisant le tri rapide sur un tableau en C, et je me tape une jolie boucle infinie familiale comme on les aime. Le pire, c'est que je l'ai déjà fait, et dans ce langage en plus, mais cette fois-ci ça ne veut pas !
Voici mon code :
// Tri rapide
void quickSort(int tab[], int gauche, int droite){
    int d = droite;              // Borne droite
    int g = gauche;              // Borne gauche
    int p = tab[gauche];         // Pivot
    int temp;                    // Pour faire les swap

    // Algorithme
    printf("%d\n",p);
    while(d>g){
        if(tab[d]>p){
            d--;
        }
        if(tab[g]<p){
            g++;
        }
        if((tab[d]>=p) && (tab[g]<p)){
            // On swap les valeurs
            temp = tab[g];
            tab[g] = tab[d];
            tab[d] = temp;
            d--;
            g++;
        }
    }
    // Swap du pivot et de la valeur au centre
    temp = tab[p];
    tab[p] = tab[g];
    tab[g] = temp;
    p=d;
    quickSort(tab,gauche,p-1);
    quickSort(tab,p+1,droite);
}


J'ai fait des tests en plaçant des printf un peu partout, et il semblerait qu'on ne rentre jamais dans mes deux if qui changent les valeurs de d et g. Et je ne comprend absolument pas pourquoi. Voilà, j'attend votre aide maintenant :)
EDIT : Ajout des balises de code (la coloration syntaxique).
Explications disponibles ici : ICI

Merci d'y penser dans tes prochains messages.
A voir également:

2 réponses

yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 584
 
bonsoir,
p semble parfois être un index, parfois une valeur.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 584
 
regarde ton code, et dis-moi ce qui se passe si tab[d]<tab[g].
je pense que les inégalités sont mal spécifiées dans tes trois if. je m'attendrais à ce que le troisième if soit exécuté si les deux premiers ne le sont pas, sinon, bonjour la boucle.
de plus, ton trosième if provoque le swap de valeurs bien triées, dommage, non?
pas très quick ton sort.
0