aide fonction tri heapsort (création du tas)

Version imprimable

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:

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

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:

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

25/12/2005, 16h43
Invité

Code:

int end=indice_max-1;

j'ai aussi du remplacer ceci par

Code:

int end=indice_max;

mais maintenant apparement cela marche...

merci pour l'aide :D [/quote]

Citation:

Code:

int end=indice_max-1;

j'ai aussi du remplacer ceci par

Code:

int end=indice_max;

mais maintenant apparement cela marche...

merci pour l'aide :D

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

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

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

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

26/12/2005, 10h36
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.
24/11/2009, 00h27
crazyvirus

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