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 :
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.
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; }
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.
Partager