Discussion :

[sioll]

Bonjour!
Je suis en train de débuter en C et j'ai un petit problème concernant les tris!
j'aimerais réussir un tri rapide de type quicksort. j'ai codé selon l'algorithme du cours en le modifiant un peu pour ma configuration. La compilation se passe sans problèmes mais lorsque j'exécute le programme, il y a "segmentation fault". Je sais pas si j'ai fais une erreur de syntaxe ou si je me suis trompé dans mes variables. ça fait plusieurs heures que je suis dessus, je suis à bout !

voila mon code sur un fichier "a" :

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*--------------------- QUICKSORT --------------------------*/
 
int trouvePivot( TabElem* tab, int i, int j )
{
	int k = i+1;
	while ( k <= j ){
		if ( tab->elems[k] > tab->elems[i] ){
			return k;
		}
		if ( tab->elems[k] < tab->elems[i] ){
			return i;
		}
		k++;
	}
	return -1;
}
 
int partition( TabElem* tab, int i, int j, int pivot )
{
	int k = i;
	int l = j;
	do {
		echange (&tab->elems[k] , &tab->elems[l]);
		while ( tab->elems[k] < pivot ){
			k++;
		}
		while ( tab->elems[l] >= pivot ){
			l = l-1;
		}
	}while ( k >l );
	return k;
}
 
void quicksort( TabElem* tab, int i, int j )
{
	int idxp;
	int k;
	idxp = trouvePivot ( tab, i ,j );
	if (idxp != -1 ) {
		k = partition ( tab , i , j , tab->elems[idxp] );
		quicksort( tab , i , k-1 );
		quicksort( tab , k , j );
	}
 
}

cette partie du code est appeler sur un autre fichier "b" :

Code :

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

quicksort( tab, 0, nbelems - 1);

J'avais fait un tri a bulle juste avant qui fonctionnais mais VRAIMENT trop long à s'exécuté.

Merci de votre aide!

[the-death]

Vu que tes noms ne sont pas tres significatifs et que l'on ne connait pas la structure de ta structure TabElem ni ce qu'elle contient : as tu pensé a utiliser un débogueur pour voir ou il segfault?
Si tu tournes sur linux, regardes un peu le fonctionnement de gdb (ou autre) qui devrait devenir ton second outil de programmation.

[souviron34]

et d'où il sort, ton k dans le quicksort ??


D'autre part, sais-tu qu'on peut faire i-- de manière symétrique à i++ ??

[diogene]

La raison est fort simple : i, j, k, l sont des variables dont le nom ne signifie rien et on a donc tendance à les confondre (de plus l se différentie mal de 1 à l'oeil).
Le choix d'un nom pour les variables est le premier et le plus important commentaire d'un code.

Je te propose donc quelques modifications :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
void quicksort( TabElem* tab, int deb, int fin)
{
	int idxp;
	int k;
	idxp = trouvePivot ( tab, deb ,fin);
	if (idxp != -1 ) {
		k = partition ( tab , deb , fin, tab->elems[idxp] );
		quicksort( tab , deb , k-1 );
		quicksort( tab , k , fin);
	}
}

Le code semble correct.
On continue :

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
int partition( TabElem* tab, int deb, int fin, int pivot )
{
//	int k = deb;
//	int l = fin;
	do {
		echange (&tab->elems[deb] , &tab->elems[fin]);
		while ( tab->elems[deb] < pivot ){
			deb++;
		}
		while ( tab->elems[fin] >= pivot ){
			fin= fin-1;
		}
	}while ( deb >fin); // COMME C'EST BIZARRE
	return deb;
}

Ce code marchera bien mieux avec while ( deb < fin);

Note :
Dans le cas où tu veux faire tester ou debugger un code, il faut fournir tous les éléments nécessaires à la compilation et l'exécution, sinon, on est forcé de reconstituer un code complet (ici, il manque la définition de TabElem et la fonction echange()). De plus, l'erreur peut très bien se trouver dans les éléments manquants.
Après l'avoir complété et corrigé le while, le code classe correctement (au mois la suite TabElem tab = {1,8,6,5,7,2,4,6,9,3}; )

[sioll]

Merci beaucoup, je vais essayé ça cet après-midi! Je comprend mieux comment marche ce tri.

[sioll]

merci, le fait de changer de signe dans mon while permettais bien de faire fonctionner le code!
TabElems :

Code :

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

1
2
3
4
typedef struct {
  int* elems;
  uint nb;
} TabElem;

si j'ai bien compris il représente un tableau d'entier dont la taille est à déterminé et dont les élément ont une valeur à déterminer.

[diogene]

Apparemment, elems doit être l'adresse du tableau de int (obtenu très vraisemblablement par allocation dynamique) et nb le nombre d'éléments de ce tableau.