Discussion :

[aaronlbk]

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 :

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
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

[foetus]

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

Code :

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
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 :

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

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); }
 
	}
}

[aaronlbk]

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

Code :

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

tmp = tab[pos_pivot + 1]

; au lieu de

Code :

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

 tmp = tab[i]

à la ligne 8, pourquoi

Code :

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

tab[pos_pivot] = tab[i];

au lieu de

Code :

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

tab[i-1] = tab[i]

[Jimmy91]

à la ligne 7, pourquoi as tu écrit

Code :

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

tmp = tab[pos_pivot + 1]

; au lieu de

Code :

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

 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].