[QSort]Problème de compréhension

Version imprimable

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:

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:

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.

03/07/2008, 15h14
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.
03/07/2008, 15h24
EvaristeGaloisBis

alors dans mon exemple on doit retourner j=0?
03/07/2008, 16h09
pseudocode

Citation:

Envoyé par EvaristeGaloisBis

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]