Discussion :

[Invité]

voilà j'arrive à ceci pour la fonction qui crée le tas et j'inclus la heapsort avec
je pense que le problème vient de la fonction sift mais je ne comprend pas trop ce qu'il manque...toutes les valeurs sont triées excepté la dernière valeur du vecteur qui semble oubliée...et je ne vois pas trop quoi changer pour qu'elle soit prise en compte :s
merci de votre aide.

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
46
47
48
49
50
51
 
void sift (int v[10], int indice_deb, int indice_max)
{
	int ifils, tmp=0, i;
	ifils=(indice_deb*2)+1;
	i=indice_deb;
 
	while (i<(indice_max-2)/2)
	{
 		if (v[ifils] < v[ifils+1])
		{
			tmp=v[ifils+1];
			v[ifils+1]=v[ifils];
			v[ifils]=tmp;
		}
    		tmp=0;
 
		if (v[ifils] > v[i])
		{
			tmp=v[i];
			v[i]=v[ifils];
			v[ifils]=tmp;
		}
		i++;
		ifils++;
	}
}
 
 
void heapsort (int v[10], int indice_max)
{
	int start=(indice_max/2)-1;
	int end=indice_max-1;
	int tmp;
 
	while (start!=0)
	{
		sift(v,start,indice_max);
		start--;
	}
	tmp=0;
 
	while (end > 0)
	{
		tmp=v[end];
		v[end]=v[0];
		v[0]=tmp;
		sift(v,0,end+1);
		end--;
	}
}

[Trap D]

Salut

Mauvaise interprétation des pseudo code je pense, une de tes erreurs est que tu as mal retranscrit en C le indice_max

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
46
47
48
49
50
51
52
// ici le plus grand indice du tableau est indice_max - 1
void sift (int v[], int indice_deb, int indice_max)
{
   int ifils, tmp, i;
   ifils=indice_deb*2+1;
   i=indice_deb;
 
   while (i<(indice_max-1)/2)
   {
      if (v[ifils] < v[ifils+1])
      {
         tmp=v[ifils+1];
         v[ifils+1]=v[ifils];
         v[ifils]=tmp;
      }
 
      if (v[ifils] > v[i])
      {
         tmp=v[i];
         v[i]=v[ifils];
         v[ifils]=tmp;
      }
 
 
      i++;
      ifils++;
   }
}
 
 
void heapsort (int v[], int indice_max)
{
   int start=(indice_max-1)/2;
   int end=indice_max-1;
   int tmp;
 
   while (start > 0)
   {
      sift(v,start,indice_max);
      start--;
   }
 
   while (end > 0)
   {
      sift(v,0,end+1);// tu dois d'abord appeler sift et ensuite intervertir
 
      tmp=v[end];
      v[end]=v[0];
      v[0]=tmp;
 
      end--;
   }

[Invité]

Code :

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

int end=indice_max-1;

j'ai aussi du remplacer ceci par

Code :

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

int end=indice_max;

mais maintenant apparement cela marche...

merci pour l'aide [/quote]

[Trap D]

Code :

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

int end=indice_max-1;

j'ai aussi du remplacer ceci par

Code :

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

int end=indice_max;

mais maintenant apparement cela marche...

merci pour l'aide

[/quote]En es-tu sûr ???
Lorsque tu fais l'échange, il y a débordement d'index du tableau

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
void heapsort (int v[], int indice_max)
{
   int start=(indice_max-1)/2;
   int end=indice_max-1;
   int tmp;
 
   while (start > 0)
   {
      sift(v,start,indice_max);
      start--;
   }
 
   while (end > 0)
   {
      sift(v,0,end+1);// tu dois d'abord appeler sift et ensuite intervertir
 
      tmp=v[end]; // plante ici en principe puisque les bornes du tableau sont 0 indice_max - 1
      v[end]=v[0];
      v[0]=tmp;
 
      end--;
   }

[Invité]

:
voilà le code complet (sans le main)...
et comme ceci il marche parfaitement...

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
46
47
48
49
50
51
 
void sift (int v[10], int indice_deb, int indice_max)
{
	int ifils, tmp=0, i;
	ifils=(indice_deb*2)+1;
	i=indice_deb;
 
	while (i<(indice_max-1)/2)
	{
 		if (v[ifils] < v[ifils+1])
		{
			tmp=v[ifils+1];
			v[ifils+1]=v[ifils];
			v[ifils]=tmp;
		}
    		tmp=0;
 
		if (v[ifils] > v[i])
		{
			tmp=v[i];
			v[i]=v[ifils];
			v[ifils]=tmp;
		}
		i++;
		ifils++;
	}
}
 
 
void heapsort (int v[10], int indice_max)
{
	int start=(indice_max-1)/2;
	int end=indice_max;
	int tmp;
 
	while (start > 0)
	{
		sift(v, start, indice_max);
		start--;
	}
 
	tmp=0;
	while (end > 0)
	{
		sift(v, 0, end+1);
		tmp=v[end];
		v[end]=v[0];
		v[0]=tmp;
		end--;
	}
}

[Trap D]

Tout dépend des arguments d'appel de la fonction dans le main.
Sous Visual C, j'ai une plante si j'appelle avec 0 et N, N étant la taille du tableau, n'oublie pas qu'en C la numérotation des tableaux commence à 0 et que si N est la taille du tableau, l'indice maximal est N-1.

[crazyvirus]

Merci TrapD !! c'est utile pour moi aussi tes commentaires !
En fait faut changer aussi le end_max dans la fonction de sift .