Discussion :

[EvaristeGaloisBis]

Bonjour,

J'aimerai comprendre l'algorithme du Qsort. Pour ce faire, j'ai regardé sur wikipédia et pour être plus précis sur le morceau de code quasiment tout en bas en C, que voici :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void quickSort(int tableau[], int p, int r) {
        int q;
        if(p<r)
        {
                q = partitionner(tableau, p, r);
                quickSort(tableau, p, q);
                quickSort(tableau, q+1, r);
        }
}
 
int partitionner(int tableau[], int p, int r) {
        int pivot = tableau[p], i = p-1, j = r+1;
        int temp;
        while(1) 
       {
                do
                        j--;
                while(tableau[j] > pivot);
                do
                        i++;
                while(tableau[i] < pivot);
                if(i<j) 
                {
                        temp = tableau[i];
                        tableau[i] = tableau[j];
                        tableau[j] = temp;
                }
                else
                        return j;
        }
        return j;
}

A sa simple vue je ne comprends pas le While(1)... Est ce que quelqu'un pourrait m'expliquer? car j'ai l'impression que ça va boucler à l'infini.

De plus j'ai voulu le faire à la main... pour être sur de bien comprendre le raisonnement.
J'ai pris le tableau : tab=[1;5;6;3]. et j'ai "executé" avec quicksort(tab,1,4).
j'ai bien une incohérence dans le morceau de code partitionner.

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
pivot=tab(1)=1
i=0, j=5
tab(4)>pivot? Non
tab(3)>pivot ? non
tab(2)>pivot? Non
tab(1)>pivot ? non
tab(0)>pivot ben... je ne sais pas...

Si quelqu'un pouvait m'éclairer sur ces quelques points.

[ToTo13]

Bonjour,

dans cette boucle, les deux premières boucles do/while vont rechercher les valeurs du tableau qui enfreignent la condition de valeur par rapport au pivot. Le but de la fonction partition étant de mettre toutes les valeurs inférieures à gauche du pivot et toutes les valeurs supérieures à droite.
Donc lorsque l'on sort de ces boucles, c'est soit pour inverser deux valeurs mal placée, donc on les inverse, soit parce que les drapeaux i et j ont dépassé le pivot et donc enfreignent la condition sur le pivot. Donc dans ce cas on est dans le cas else return.

[EvaristeGaloisBis]

alors dans mon exemple on doit retourner j=0?

[pseudocode]

alors dans mon exemple on doit retourner j=0?

oui, dans ce cas très particulier, le partitionnement n'a pas modifié le tableau de départ et le pivot est en position 0:

[1;5;6;3] --(partition)--> gauche=[1] et droite=[5;6;3]