Discussion :

[hbx360]

Bonjour, je viens vous demander de l'aide sur mon code pour le tri par tas j'ai éplucher pas mal de vidéo et de pdf et autre site qui traitaient du tri par tas et j'ai fait comme indiquer mais mon code de tri par tas est hyper lent pour 200 000 entier triè il met 20 seconde.
Pourriez-vous m'aider et me dire ou est mon problème je pense qu'il y a quelque chose dans la procédure que je n'ai pas du saisir.
je travail sous emacs et cygwin
Je suis débutant.
Merci par avance.

Code :

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
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
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
 
#define SIZE 200000
 
int
main (int argc, char *argv[])
{
 
 int tmp, i, n, m=0, a = 0, j, f = 0, k;
 int len =  SIZE, r = SIZE-1;
 int* T = malloc(sizeof(int) * SIZE); 
 int* H = malloc(sizeof(int) * SIZE); ;
 
/*Tableau T décroissant*/
 for(i = 0; i < len; i++)
  {
    T[i]=r; 
    r--;
    }
 
  /*Affichage du tableau T*/
 /*for(i = 0; i < SIZE; i++)
   printf("%d ",T[i]);*/
 
 /*On par du bas à droite de L'arbre vers la gauche puis on
remonte en partant de la droite le plus petit élément*/
 
 for(j = 0; j <SIZE; j++)
     {  
       for(i = (len/2)-1 ; i >=0; i--)
	  {
             k=2*i;
             if(k+2 < len)
	      {
		  if(T[k+2] < T[i])
		      {
			tmp = T[i];
			T[i] = T[k+2];
			T[k+2] = tmp;
		      }
 
	      }
 
             if(k+1 < len)
	      {
		  if(T[k+1] < T[i])
		      {
			tmp = T[i];
			T[i] = T[k+1];
			T[k+1] = tmp;
		      }
	      }
	  }
 
	/*Mise du plus petit élément du tas dans
le tableau H et reduction de la taille du tableau
T et permutation du dernier élément du tableau T
dans la première case du tableau T*/
 
	      H[j] = T[a];
              T[a] = T[len-1];
              len--;
	  }
 
  /*Affichage du tableau H*/
  /*for(i = 0; i < SIZE; i++)
    printf("%d ",H[i]);*/
 
  free(T);
  free(H);
 
return EXIT_SUCCESS;
}

[Bktero]

Bonjour,

Peux-tu nous donner la ligne de commande qui te sert à compiler ?

[Kannagi]

Le probleme ne vient pas des option du compilateur , ça met 27 seconde chez moi avec -s -O3.
On fait il fait un peu plus qu'une boucle de 200 000 , vu qu'a chaque boucle il fait une autre boucle de len/2 ,et qu'il décrément a chaque boucle , du coupe rien que en ne lisant que 2 tour de boucle , il fait deja presque 200 000 fois son truc.
Donc on gros tu fais ceci :

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
k=2*i;
             if(k+2 < len)
	      {
		  if(T[k+2] < T[i])
		      {
			tmp = T[i];
			T[i] = T[k+2];
			T[k+2] = tmp;
		      }
 
	      }
 
             if(k+1 < len)
	      {
		  if(T[k+1] < T[i])
		      {
			tmp = T[i];
			T[i] = T[k+1];
			T[k+1] = tmp;
		      }
	      }

1410065408 fois , ce qui est assez énorme.
Il faut revoir les algo de tri , y a des méthode plus efficace que de relire ta boucle en (presque) entier chaque fois.

[hbx360]

Merci pour ta réponse, j'ai retourné le problème dans tous les sens je n'arrive pas à trouvé la solution pour les boucle.
Pourtant je fait comme indiquer dans les cours que j'ai vu sur le net concernant le tri par tas.
Quand tu dis : "il y a des méthodes plus efficace que de relire ta boucle en (presque) entier chaque fois" quelle sont ces méthode par ce que là j'utilise la méthode du tri par tas et ça ne marche pas je ne voit pas du tout comment faire ?

[Kannagi]

N'oublie pas que google et wikipédia sont des amis
Voila sur Wikipédia ce qu'on trouve par exemple : Algorithmes de tri , et je te conseille le Tri rapide ou le Tri_par_insertion (plutôt simple pour débuté).
Personnellement je ne les ai vu que ne première année donc ça remonte et depuis je ne l'ai plus utilisé donc je pourrais pas de l'expliquer en détails mais le wiki est plutôt clair et n'est pas difficile a mettre en place (il est enseigné en première année et en général cet algo est mieux compris que les pointeurs ).

En C il existe qsort qui permet justement pour trier un tableau , mais je te conseille de ne pas utiliser , ça te permettra de comprendre les algo de tri justement.

[hbx360]

A Bktero ma ligne de commande pour compiler est : gcc -c -O3 -g

[hbx360]

Je peut assuré que j'ai cherché énormément sur le net surtout concernant le tri par tas j'ai bien compris la méthode utilisé pour le tri par tas je l'ai reproduit dans mon code et pourtant sa ne marche pas mon code suit bien les explications : on à un tableau T que l'on considère comme un arbre on range l'arbre et ensuite on prend la plus petite valeur que l'on met dans un 2eme tableau H puis dans le tableau T on met le dernier nombre dans la 1er case du même tableau donc T ensuite on réarange l'arbre donc le tableau T et ainsi de suite j'utilise bien dans mon code pourtant la même procédure qui est expliquer pour le tri par tas.

Est-ce que ce serait possible d'avoir un bout de code me montrant la façon de faire.

Merci par avance et merci pour ton aide Kannagi

[Danny-k]

Tiens voilà le lien du wiki anglais, l'algo est très complet, je l'ai implémenté ce matin en moins de 10min :
http://en.wikipedia.org/wiki/Heapsort

[hbx360]

Merci pour ton aide