Tri par insertion

Version imprimable

Tri par insertion

Bonjour,

Je dois effectuer une fonction de tri par insertion de valeurs entrées via le main, mais ça déconne pas mal en fait. Je ne trouve pas l'erreur.

Voici le code :

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
 
#include<stdio.h>
#include<stdlib.h>
 
 
int *insere(int *tableau, int valeur, int taille); 
 
int main(void)
{
 
 
 
     int *T;
 
     T=malloc(20*sizeof(int));
 
     int j;
     for ( j=0 ; j < 20 ; j++ )
         {
               T[j]=10*j;
         }
 
 
 
     char control='o';
     int valeur;
     int nouvelle_taille=20;
 
     printf(" SAISIR 'n' POUR QUITTER LA SAISIE DES VALEURS et 'o' POUR CONTINUER \n\n");
 
     while ( control != 'n')
           {
                         printf(" Veuillez saisir un entier : ");
                         scanf("%d",&valeur);
                         nouvelle_taille++;
                         T = insere(T, valeur, nouvelle_taille);
                         printf("\nCONTINUER (o/n) : ");
                         scanf("%s",&control);
 
           }
 
    int i;
    for ( i=0 ; i < nouvelle_taille ; i++ )
        {
              printf("\nT[%d]=%d", i, T[i]); 
              getch();
        }
}
 
 
 
 
int *insere(int *tableau, int valeur, int taille) 
{
 
    tableau=realloc(tableau, taille*sizeof(int));
    int inser;
 
    int l=0;
    for ( l=0 ; l < taille ; l++ )
        {
              if ( valeur >= tableau[l] ) 
                 {
                       inser=l;
                 }
 
        }
 
    int m;    
    for ( m=(taille-1) ; m<inser ; m-- )
        {
                  tableau[m+1]=tableau[m];
        }
 
    tableau[inser+1]=valeur;
    return tableau;
}

Si vous avez des suggestions, je suis preneur !
Merci d'avance

16/03/2009, 17h01
Médinoc

En quoi exactement cela déconne-t-il ?
16/03/2009, 17h08
darkwall_37

Oui désolé, je vais trop vite !
En fait, la valeur à insérée s'insère mais le tableau ne se décale pas correctement donc au final une des valeurs est écrasée et la nouvelle case ajoutée soit la dernière affiche la valeur de l'adresse de la case mémoire. Je me suis donc trompé dans ma boucle pour décaler les valeur je suppose.
16/03/2009, 17h38
darkwall_37

Code:

for ( m=(taille-1) ; m>inser ; m-- )

J'ai mis un < au lieu d'un > o.0 !

Maintenant quand j'essaye de rentrer plus de 3 valeurs à la suite le programme plante !?

Je te conseillerais de gérer tableau et réallocation avec une structure:

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
struct TableauInt
{
	int *tab;
	size_t cElems;
};
 
int reallocTableauInt(struct TableauInt *pTableau, size_t newcElems)
{
	size_t newcb = newcElems * sizeof *pTableau->tab; /*nouvelle taille en octets*/
	int *tmp = realloc(pTableau->tab, newcb);
	if(tmp == NULL)
		return -1; /*erreur*/
 
	pTableau->tab = tmp;
	pTableau->cElems = newcElems;
	return 0;
}
 
void decalerIntDroite(struct TableauInt *pTableau, size_t indexDebut)
{
	size_t i;
	for(i=pTableau->cElems-1 ; i>indexDebut ; --i)
		pTableau->tab[i] = pTableau->tab[i-1];
}
 
/* Decale les éléments indexDebut et suivants vers la gauche.
   pTableau->tab[indexDebut-1] est écrasé. */
void decalerIntGauche(struct TableauInt *pTableau, size_t indexDebut)
{
	size_t i;
	for(i=indexDebut ; i < pTableau->cElems ; ++i)
		pTableau->tab[i-1] = pTableau->tab[i];
}
 
int insererTableau(struct TableauInt *pTableau, size_t index, int valeur)
{
	/* Augmente de 1 la taille du tableau */
	if(reallocTableauInt(pTableau, pTableau->cElems+1) < 0)
		return -1;
 
	/* Décale les autres valeurs vers la droite et insère la nouvelle valeur */
	decalerIntDroite(pTableau, index);
	pTableau->tab[index] = valeur;
}

16/03/2009, 22h51
publicStaticVoidMain

Citation:

Envoyé par Médinoc

Je te conseillerais de gérer tableau et réallocation avec une structure:

Ou avec une Liste chainée !!! ;)