Discussion :

[aaronlbk]

Salut à tous,
je viens vous soumettre un problème que j'ai avec le code de l'algorithme de TRI DE TAS qui ne marche pas,
Je vous présente les fonctions que j'ai écrites :

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
void permutation(int tab[],int i, int j)
{
	int temp = 0;
	temp = tab[i];
	tab[i]=tab[j];
	tab[j]=temp;
}
 
void tamiser(int tab[], int noeud, int n)
{
	int k = noeud;
	int j = 2*k;
	while(j<=n)
	{
		if (j<n && tab[j]<tab[j+1])
		{
			j++;		
		}
		if (tab[k]<tab[j])
		{
			permutation(tab,k,j);
			k = j;
			j = 2*k;
		}
		else return;
 
	}
 
}
 
void tri(int tab[], int n)
{
	for (int i = n/2; i>0;i--)
	{
		tamiser(tab,i,n);
	}
	for (int i=n; i>1;i-- )
	{
		permutation(tab,i,1);
		tamiser(tab,1,i);
	}
 
}

La fonction tamiser effectue l'étape préliminaire de rangement des éléments du tableau dans l'arbre; La fonction tri est celle qui est censée réaliser le tri final ,

Merci d'avance pour votre aide

[foetus]

Il y a 2 problèmes

• Dans la procédure tri dans la 2ième boucle c'est i-1. Donc tamiser(tab,1,i-1);. Ici i pointe sur la première case à partir de laquelle le tableau est trié.
• Tu est sensé savoir qu'en C, les tableaux commencent par l'indice 0. Donc avec ta boucle for (int i = n/2; i>0;i--) tu oublies de tamiser la première cas du tableau (la racine du tas). De même permutation(tab,i,1); tu ne permutes pas la racine du tas qui contient la valeur la plus élévée du tas.

Code à tester

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
void tri(int tab[], int n)
{
	if (n <= 1) return;
 
	for (int i = n/2; i>=0;i--)
	{
		tamiser(tab,i,n);
	}
	for (int i=(n-1); i>0;i-- )
	{
		permutation(tab,i,0);
		tamiser(tab,0,i-1);
	}
 
}

PS: La condition i>=0de ma première boucle je la trouve moche comme tout
Peut-être faire l'algo avec les indices [1, n] mais réajuster cela pendant les permutations ou les tests d'égalité.


Sinon ton code est moche , mais bon ce n'est pas trop grave: trop de variable i, j, k (remplace par fils1, fils2, father, pos), tu peut initialiser temp directement au lieu de d'abord l’initialiser à 0, et tu déclares 2 fois une variable i pour tes boucles

[aaronlbk]

Merci chef