problème avec un algo quicksort

Version imprimable

Salut à tous,
je viens vous soumettre un problème que j'ai avec un algorithme quicksort,
Je vous présente les fonctions de partition et quicksort:
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 int partition(int tab[], int deb, int fin) { int pivot = tab[deb]; int pos_pivot = deb; for(int i =deb+1; i <=fin; i++) { if (tab[i] < pivot) { tab[i-1]=tab[i]; tab[i]=pivot; pos_pivot++; } } return pos_pivot; } void quicksort(int tab[],int deb,int fin) { int pivot; if(deb<fin) { pivot = partition(tab,deb,fin); quicksort(tab,deb,pivot-1); quicksort(tab,pivot+1,fin); } }
j'ai l'impression que mon problème est au niveau de la fonction de partition,
pour le tableau en entrée suivant:
1165
17137
14102
11300
31285
25412
23936
254

Voici ce que j'obtiens en sortie:
1165
17137
14102
11300
31285
25412
23936
254

Je sais que des codes tout fait existent sur le net, mais j'ai vraiment envie de le faire moi même,
Merci

Il me semble qu'il faut faire ceci :mrgreen: (fait de tête sans tester et attention aux limites)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int partition(int tab[], int deb, int fin) {
	int pivot = tab[deb];
	int pos_pivot = deb;
 
	for(int i = deb+1, tmp = 0; i <=fin; i++) {
		if (tab[i] < pivot) {
			tmp = tab[pos_pivot + 1];
			tab[pos_pivot] = tab[i];
			tab[i] = tmp;
			pos_pivot++;
			tab[pos_pivot] = pivot;
		}
	}
 
	return pos_pivot;
}

Mais aussi (fait de tête sans tester et attention aux limites)

Code:

1
2
3
4
5
6
7
8
9
10
void quicksort(int tab[],int deb,int fin){
	int pivot;
 
	if(deb<fin) {
		pivot = partition(tab, deb, fin);
		if ((pivot - 1 - deb) > 1) { quicksort(tab, deb, pivot-1); }
		if ((fin - pivot - 1) > 1) { quicksort(tab, pivot+1, fin); }
 
	}
}

14/08/2014, 01h03
aaronlbk

Salut,
Merci pour ta réponse, J'aimerais te poser quelques questions pour mieux comprendre :mrgreen:
Dans la fonction partition,
à la ligne 7, pourquoi as tu écrit

Code:

tmp = tab[pos_pivot + 1]

; au lieu de

Code:

tmp = tab[i]

à la ligne 8, pourquoi

Code:

tab[pos_pivot] = tab[i];

au lieu de

Code:

tab[i-1] = tab[i]
14/08/2014, 11h31
Jimmy91

Citation:

Envoyé par aaronlbk

à la ligne 7, pourquoi as tu écrit

Code:

tmp = tab[pos_pivot + 1]

; au lieu de

Code:

tmp = tab[i]

Salut aaronlbk,

À mon humble avis, foetus a écrit tmp = tab[pos_pivot+1] car il voulait prendre le voisin direct de pivot pour l'affecter ensuite à tab[i] dont la valeur sera elle même affectée à tab[pos_pivot]. En gros :

AVANT le mouvement de boucle

...
tab[pos_pivot]
tab[pos_pivot+1]
...
tab[i]
...

APRÈS le mouvement de boucle

...
tab[i]
tab[pos_pivot]
...
tab[pos_pivot+1]
...

Si tab[i] est inférieur à pivot = tab[pos_pivot], alors tab[i] passe devant le pivot, ce que l'on voulait obtenir ici.

En fait, tab[i] n'est pas forcément le voisin direct de tab[pos_pivot], contrairement à tab[pos_pivot + 1]. En effet, il peut arriver que le pivot ne se déplace pas (si on rencontre : tab[i] >= pivot). Dans ce cas, le voisin direct de pivot lui sera supérieur ou égal et ne passera jamais devant lui. On devra alors chercher plus loin que ce voisin direct (via l'index i) pour trouver éventuellement des valeurs plus petites. Et ces valeurs plus petites, qu'on assigne à tmp, doivent être "dépassées" par le pivot.

Pour ta seconde question, si tu écrivais "tab[i-1] = tab[i], on aurait :

AVANT le mouvement de boucle

...
tab[pos_pivot]
tab[pos_pivot+1]
...
tab[i-1]
tab[i]
...

APRÈS le mouvement de boucle

...
tab[pos_pivot]
tab[pos_pivot+1]
...
tab[i]
tab[i-1]
...

Ce qui n'aurait aucun sens puisque la position du pivot ne change pas. Le but, je le rappelle, est de faire passer tab[i] avant tab[pos_pivot] si on a tab[i] < tab[pos_pivot].