programme en c "tri par tas"

Version imprimable

bonsoir a tous ,
svp qui peut m'aider a faire un programme en c pour tri par tas (heap sort) ou bien me dire c'est quoi l'erreur dans ce programme a chaque fois que je le compile il m'affiche un erreur au niveux de ça tab[i]=random(); je vois pas l'erreur

mercii

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define TRUE 1
#define FALSE 0
 
void initTableau(int *tab, int taille){
	int i;
	for(i = 0; i < taille; i++)
		tab[i]=random();
}
 
void swap(int *a, int *b){
	int x = *a;
	*a = *b;
	*b = x;
}
 
char domine( int *tab, int taille, int j ){
 
	if( 2*(j+1)-1 >= taille) /* tab[j] est seul */
		return TRUE;
 
	else if(2*(j+1)-1 == taille-1 && tab[j] >= tab[2*(j+1)-1]) /* tab[j] a 1 descendant et domine */
			return TRUE;
 
	else if(tab[j] >= tab[2*(j+1)-1] && tab[j] >= tab[2*(j+1)]) /* tab[j] a 2 descendants et domine */
			return TRUE;
 
	return FALSE; /* Dans le cas ou tab[j] n'est pas seul et ne domine pas */
}
 
void retablirTas( int *tab, int j, int taille ){
 
	while(!domine(tab, taille, j)){/* I(j) et j domine => tab[0...taille-1] est un tas.*/
 
		if( 2*(j+1) == taille){ /* degre 1 && I(2(j+1)-1) */
			swap(&tab[j], &tab[ 2*(j+1)-1 ]);
			j = 2*(j+1)-1;
		}
 
		else{ /* degre 2 */
			if( tab[ 2*(j+1)-1 ] >= tab[ 2*(j+1) ] ){ /* I(2(j+1)-1) */
				swap( &tab[ 2*(j+1)-1 ], &tab[j] );
				j = 2*(j+1)-1; /* I(j) */
			}
 
			else{ /*I(2*(j+1)) */
				swap(&tab[ 2*(j+1) ], &tab[j]);
				j = 2*(j+1); /* I(j) */
			}
		}
	}
}
 
void faireTas(int *tab, int taille){
	int k;
	for(k = taille-1; k >= 0; k--)
		retablirTas(tab, k, taille);
}
 
int main(){
	int *tab;
	int taille;
	int f;
 
	/* Mesure du temps d'execution*/
	clock_t start, end;
	double elapsed;
 
	printf("Entrer la taille du tableau :\t");
	scanf("%d", &taille);
	f = taille;
 
	if ( ( tab = (int *)malloc( (sizeof(int)*taille)) ) == NULL)
		exit(EXIT_FAILURE);
 
	initTableau(tab,taille);
 
	start = clock(); /* lancement de la mesure */
 
	faireTas(tab, taille);
 
	/* I(f) = tab[0 ... f-1] est un tas
	&& ensemble des elements de tab[0 ... f-1] inferieur ou egal 
	a ensemble des elements tab[f ... taille-1]
	&& tab[f ... taille-1] est trie croissant
	*/
 
	while ( f > 1){ /* I(k) && (k>1)*/
                swap(&tab[0], &tab[f-1]);
                retablirTas(tab, 0, f-1); /* I(k-1) */
                f--;
        }
 
	end = clock(); /* arret de la mesure */
	elapsed =(double)(end-start)/CLOCKS_PER_SEC;
	printf("Temps de calcul : %lf\n",elapsed);
 
	exit(EXIT_SUCCESS);
}

18/12/2011, 22h16
BlueMonkey

Bonsoir,

La fonction random de la librairie <stdlib.h> prend un paramètre non optionnel du type int

La valeur retournée par random est comprise entre 0 et <le paramètre - 1>.

Après quelques aménagements pour rendre ton code compilable, il me semble que ta fonction faireTas() ne transforme pas tab en tas. Classiquement, je procéderais comme ceci:

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
/* -tc- domine est reimplante de maniere a retourner l'indice i parmi {j, GAUCHE(j),
   DROITE(j)} correspondant a la valeur maximale de tab[i] */
int domine( int *tab, int taille, int j )
{
    int max = j;
 
    if (GAUCHE(j) < taille && tab[GAUCHE(j)] > tab[j])
    {
        max = GAUCHE(j);
    }
 
    if (DROITE(j) < taille && tab[DROITE(j)] > tab[max])
    {
        max = DROITE(j);
    }
 
    return max;
}
 
 
void retablirTas( int *tab, int j, int taille )
{
 
    int max = domine(tab, taille, j);
 
    if (j != max)
    {
 
        swap(&tab[j], &tab[max]);
        retablirTas(tab, max, taille );
    }
}
 
void faireTas(int *tab, int taille)
{
    int i;
    for(i = taille/2 - 1; i >= 0; i--)
    {
        retablirTas(tab, i, taille);
    }
}

J'ai modifié la sémantique de la fonction domine pour coller à l'implantation classique. Si l'appel récursif à retablirTas() est dérangeant, on peut arranger cela avec:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
void retablirTas( int *tab, int j, int taille )
{
 
    int max = domine(tab, taille, j);
    while (max != j)
    {
        swap(&tab[j], &tab[max]);
        j = max;
        max = domine(tab, taille, j);
    }
}

Sinon, tu utilises random() pour la génération de nombres aléatoires. Ce n'est pas une fonction standard, mais une fonction BSD qui doit en principe s'initialiser à l'aide de srandom(). Dans mon code de test, je l'ai remplacée par la fonction rand_n() donnée dans la FAQ C. Plutôt que t'emmêler les pinceaux avec tes indices de tableaux, je te recommande d'utiliser des macros telles que:

Code:

1
2
#define GAUCHE(i) ( 2 * (i) + 1 )
#define DROITE(i) ( 2 * (i) + 2 )

Voici mon code de test:

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define TRUE 1
#define FALSE 0
 
#define GAUCHE(i) ( 2 * (i) + 1 )
#define DROITE(i) ( 2 * (i) + 2 )
 
#define DEBUG
 
#ifdef DEBUG
#   define afficherTableau(tab, taille) afficherTableau__((tab), (taille))
#else
#   define afficherTableau(tab, taille)
#endif
 
static void afficherTableau__(int *tab, int taille)
{
    int i;
 
    printf("DEBUG: ");
 
    for (i = 0; i < taille; i++)
    {
        printf("%d ", tab[i]);
    }
    printf("\n");
}
 
 
int rand_n(int n)
{
    int partSize   = 1 + (n == RAND_MAX ? 0 : (RAND_MAX - n) / (n + 1));
    int maxUsefull = partSize * n + (partSize - 1);
    int draw;
 
    do {
        draw = rand();
    } while (draw > maxUsefull);
 
    return draw / partSize;
}
 
/* -tc- initialisation du tableau avec des nombres aléatoires */
void initTableau(int *tab, int taille)
{
    int i;
    for(i = 0; i < taille; i++)
    {
        tab[i] = rand_n(100);
    }
 
}
 
void swap(int *a, int *b)
{
    int x = *a;
    *a = *b;
    *b = x;
}
 
 
/* -tc- domine est reimplante de maniere a retourner l'indice i parmi {j, GAUCHE(j),
   DROITE(j)} correspondant a la valeur maximale de tab[i] */
int domine( int *tab, int taille, int j )
{
    int max = j;
 
    if (GAUCHE(j) < taille && tab[GAUCHE(j)] > tab[j])
    {
        max = GAUCHE(j);
    }
 
    if (DROITE(j) < taille && tab[DROITE(j)] > tab[max])
    {
        max = DROITE(j);
    }
 
    return max;
}
 
 
void retablirTas( int *tab, int j, int taille )
{
 
    int max = domine(tab, taille, j);
    while (max != j)
    {
        swap(&tab[j], &tab[max]);
        j = max;
        max = domine(tab, taille, j);
    }
}
 
void faireTas(int *tab, int taille)
{
    int i;
    for(i = taille/2 - 1; i >= 0; i--)
    {
        retablirTas(tab, i, taille);
    }
}
 
/* -tc- la fonction qui implante le tri par tas */
void trier(int *tab, int taille)
{
    int i;
    for (i = taille - 1; i > 0; i--)
    {
        faireTas(tab, taille);
        swap(&tab[0], &tab[taille - 1]);
        taille--;
    }
}
 
int main(void)
{
    int *tab = NULL;
    int taille;
    int err = 0;
    int rv;
 
    /* -tc- initialisation du générateur de nombres pseudo-aleatoires */
    srand((unsigned)time(NULL));
 
    /* -tc- attention a toujours verifier la valeur retournee par scanf() */
    do
    {
        int c;
        printf("Entrer la taille du tableau :\t");
        fflush(stdout);
        rv = scanf("%d", &taille);
 
        while ((c = fgetc(stdin)) != '\n' && c != EOF)
        {
            /* -tc- On vide le tampon de stdin */
        }
    }
    while (rv != 1);
 
    tab = malloc(taille * sizeof *tab);
    if (tab != NULL)
    {
        initTableau(tab, taille);
        afficherTableau(tab, taille);
 
        faireTas(tab, taille);
        trier(tab, taille);
        afficherTableau(tab, taille);
 
        /* -tc- liberation des ressources et affectation d'une adresse invalide
        */
        free(tab), tab = NULL;
    }
    else
    {
        /* -tc- en cas d'erreur d'allocation, on sort du programme proprement */
        err = EXIT_FAILURE;
    }
 
    return err;
}

Bon, j'ai pas fait mille tests non plus. En espérant que cela te permette d'avancer.

Avec mes meilleures salutations

Thierry

aide sur le tri par tas heap sort

Bonjour, bonjouuur,

j'en profite de cette discussion pour poser mon problème
Comme je suis débutante en informatique et en langage C particulièrement, j'essaie d’écrire un programme pour faire le tri par tas appelé aussi le heap-sort.
J'ai écrit un programme mais il ne me fait que déplacer la première valeur vers la fin et faire déplacer les autres valeurs vers l'avant ce qui est loin d'être un tri par tas.
Je vous mets le code. Quelqu’un peut m'aider à corriger se programme svp??

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
87
88
89
90
91
92
93
94
95
96
97
98
 
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
 
void init_tab (int *tab, int taille);
void affiche_tab (int *tab, int taille);
void construct(int *tab, int taille);
void tri_heap (int *tab, int taille);
void placer(int *tab, int g,int d );
 
 
int main ()
{
 
	int taille;
	clock_t debut, fin;
	double temps;
	debut =clock();
 
 
	printf("Donner la taille du tableau:");
	scanf("%d", &taille);
	//int tab[taille];
	int *tab=malloc(taille* sizeof(int));
	init_tab(tab, taille);
	affiche_tab(tab, taille);
 
	tri_heap(tab, taille);
	affiche_tab(tab, taille);
 
	fin=clock();
	temps=((double)fin-debut);
	printf("temps d'execution= %.3f secondes\n ", temps/CLOCKS_PER_SEC);
 
	return 0;
}
//Fonction initialisation d'un tableau
void init_tab( int *tab, int taille)
{
	for (int pos=0; pos<taille; pos++)
		tab[pos]=rand()%100;
}
 
//Fonction affichage d'un tableau
void affiche_tab(int *tab, int taille)
{
	for (int pos=0; pos<taille; pos++)
	{
		printf("%3d", tab[pos]);
	}	
	printf("\n");
}
//Fonction tri_heap
void tri_heap(int *tab, int taille)
{
        //Construction du tas
	int tmp;		
	for (int i=taille/2-1; i>0; i--)		
	{
		placer(tab, taille, i);	
	}
        //
	for (int i=taille-1; i>=1; i--)
	{	
		//printf("%5d", i);
		//printf("%5d", tab[i]);
		//printf("\n");
		tmp=tab[i];
		tab[i]=tab[0];
		tab[0]=tmp;
		placer(tab,i,0);
		//printf("%5d", tab[i]);
	}
}
void placer(int *tab, int g,int taille )
{
	int i,j,x, place_trouvee;
	x=tab[g];
	i=g;
	j=2*g+1;
	place_trouvee=0;
	while ((j<=taille) && !(place_trouvee))
	{
		if (j<taille)
			if (tab[j+1]>tab[j]) 
				j=j+1;
		if (x>=tab[j])
			place_trouvee=1;
		else
		{
			tab[i]=tab[j];
			i=j;
			j=2*i+1;
		}
	}
	tab[i]=x;
}