Tri par tas en C

Version imprimable

Tri par tas en C

Bonjour,
j'essaye d'ecrire un algo tri par tas en utilisant deux fonction Ajouter et Supprimer.
le programme marche bien sauf une faute(bug) que j'ai pas pu la corriger,
j'ai un tableau initial, et en sortie un tableau triee.
le probleme c'est que la 1re case est tjrs evalue à 0,
et si je force le programme de commencer à 0 j'obtients des grandes chiffres négatifs.
je sais que c'est un probleme d'indices, J'ai passé des heures et des heures et je ne trouvais pas la solution. :(:(:pleure:
svp j'ai vraiment besoin d'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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
#include<stdio.h>
#include<stdlib.h>
 
int Ajouter (int Tas[], int p, int x)
{
  int j, temp;
 
    p=p + 1 ;
    j=p ;
	Tas[p] = x ;
 
    while((j>1)&&( Tas[j] < Tas[j/2]))
     {
         temp = Tas[j] ;
         Tas[j] = Tas[j/2] ;
         Tas[j/2] = temp ;
         j= j/2 ;
	}
return p;
} //end Ajouter
 
int *Supprimer(int Tas[], int P, int min)
{
 int i, j, temp;
 static int res[2];
 
   min = Tas[1] ;
   Tas[1] = Tas[P] ;
   P = P - 1;
   j = 1; 
   while (j <= (P/2))
   {
      if ((2 * j == P ) || (Tas[2 * j] < Tas[2 * j + 1]) )
           i = 2 * j;
      else i= 2 * j +1;
      if (Tas[j] > Tas[i])
      {
         temp = Tas[j];
         Tas[j] = Tas[i];
         Tas[i] = temp;
         j = i;
      }
      else break;
   }
res[0]=P;
res[1]=min;
return res; //pour retourner 2 valeurs
}
 
void Afficher(int Tab[], int n)
{
int i;
  printf("---------------------\n");
	for(i=0;i<n;i++)
   		printf("%d, ",Tab[i]);
  printf("\n");
}
 
int main()
{
  printf("\n*** TRI PAR ARBRE ***\n");
 
int n=10, p=0,lemin;
int tab[10]={2,5,8,9,7,6,4,15,11,25};
int Tas[10];
int Tabtrie[10];
int *te;
 
  Afficher(tab, n);
  while(p <n)
    p=Ajouter ( Tas, p, tab[p+1] );
//Afficher(Tas, n);
 
  while (p >= 1)
  {
      te=Supprimer ( Tas, p, lemin );
		p=te[0];
		lemin=te[1];
      Tabtrie[n-p]=lemin;
  }
 
  Afficher(Tabtrie, n);
  printf("\n");
return 0;
}

Ce n'est pas un tri par tas :mrgreen: :mrgreen: Tu maintiens un tas pendant l'ajout de valeur (et encore j'ai des doutes :koi:)

Ensuite la réponse est simple : c'est ton ajout qui est mauvais. Voici son travail
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 *** TRI PAR ARBRE *** --------------------- 2, 5, 8, 9, 7, 6, 4, 15, 11, 25, Swap : 7 at 4 and 8 at 2 Swap : 6 at 5 and 7 at 2 Swap : 4 at 6 and 9 at 3 Swap : 4 at 3 and 5 at 1 Swap : 0 at 10 and 7 at 5 Swap : 0 at 5 and 6 at 2 Swap : 0 at 2 and 4 at 1 --------------------- -2146187343, 0, 4, 5, 8, 6, 9, 15, 11, 25, --------------------- 472, 0, 4, 5, 6, 7, 8, 9, 11, 15,
Légende : "Swap : 0 at 2 and 4 at 1" -> j'échange la valeur 0 à la position 2 avec la valeur 4 à la position 1.

:mrgreen:
Ton tas n'est jamais initialisé : c'est pour cela que tu as des valeurs indéfinies.
Et ta fonction Ajouter effectivement ne fait pas d'échange avec la première case (0) et même déborde (10)

01/12/2018, 00h25
kami08

oui oui , merci,
j'ai trouvé la reponse
il faut changer la boucle while dans Ajouter et aussi l'affectation de TabTriee :lol::D
01/12/2018, 02h36
foetus
Poste ton code juste pour voir ton algo :mrgreen:

Parce que, en l'état, c'est du grand n'importe quoi :aie: :aie:
- Tu ne peux pas trier juste en tamisant, puisque le principe c'est d'avoir à la racine la valeur la plus grande et de "ranger cette valeur". Mais le reste du tas n'est pas trié.
- Tu ne peux pas trier juste en faisant remonter une valeur, puisque tu ne testes jamais les 2 fils (lequel est le plus grand). Le tri par tas lui s'en fiche.
- Bonus : le tri par tas est un algo sur place. je ne vois pas l'intérêt d'utiliser 2 (3) tableaux.
- Bonus : Dans la fonction Ajouter, à quel moment tu prends le plus grand des fils ?
- Ta fonction Ajouter incrémente l'indice p. Ce n'est pas son rôle. Tu dois remplacer ta boucle while (celle qui appelle la fonction Ajouter) par une boucle for
- Tu n'as pas besoin d'une variable statique : apprends le passage de valeurs par pointeur - paramètre de sortie (out) (ce n'est pas sorcier, c'est de la manipulation d'adresse basique)
- Ta fonction Supprimer semble décrémenter l'indice p. Ce n'est pas son rôle.
- Ta fonction Afficher n'est pas correcte : elle affiche une virgule (et un espace) en trop.
- Apprends à nommer tes variables et à formatter ton code
La page wiki - tris par tas - a des exemples et du pseudo-code :zoubi: (<- lien)