Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1475 connectés 

  FORUM HardWare.fr
  Programmation
  C

  Tri par insertion

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Tri par insertion

n°1750341
slr56
Tout problème a sa solution.
Posté le 23-06-2008 à 18:10:34  profilanswer
 

Bonjour,
je dois faire un tri de nombres, saisis par l'utilisateur, en utilisant la méthode par insertion. Je les tris par ordre croissant.
 
J'ai compris le principe de cette méthode :
 
l'utilisateur rempli le tableau
on trouve le plus petit
on le met à la première place
ensuite on réduit la taille du tableau de "1"
on trouve le plus petit nombre et on le met a la première place de la nouvelle taille.  
Ainsi de suite jusqu'au dernier.
 
Voila ce que j'ai fait cependant je ne vois pas comment réduit la taille du tableau au fur et à mesure que "j'avance" dans le tableau. Faut-il faire une boucle dans la boucle? J'aurais tendance à penser ça mais je ne suis pas sûr. merci de m'aider.
 

Code :
  1. /* déclaration des fichiers nécessaires*/
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. int tab[10];
  5. int compteur;
  6. int i,nb,nb2,taille;
  7. int main()
  8. {
  9. /*  insertion des valeurs dans le tableau */
  10. for (compteur=1;compteur<11;compteur++)
  11. {
  12.     printf("Saisissez la valeur numero %d : ", compteur);
  13.     scanf("%d",&tab[compteur]);
  14. }
  15. /* tri des données*/
  16. for (i=1;i=10;i++)
  17. {
  18.     nb=tab[i];
  19.     if (tab[i]<nb)
  20.     {    nb=tab[i];
  21.         nb2=nb;
  22.         tab[i]=nb;
  23.     }
  24.     tab[i]=tab[i]+1;
  25. }
  26. /* affichage du contenu du tableau  */
  27. for (compteur=1;compteur<11;compteur++)
  28. {
  29.     printf("%d,%d",compteur,tab[compteur]);
  30. }
  31. }

Message cité 1 fois
Message édité par slr56 le 23-06-2008 à 18:12:34
mood
Publicité
Posté le 23-06-2008 à 18:10:34  profilanswer
 

n°1750349
Taz
bisounours-codeur
Posté le 23-06-2008 à 18:31:16  profilanswer
 

euh tu sais qu'en C les indices commencent à partir de 0 ?

n°1750352
Paulp
~, sweet ~
Posté le 23-06-2008 à 18:33:32  profilanswer
 

slr56 a écrit :

Bonjour,
je dois faire un tri de nombres, saisis par l'utilisateur, en utilisant la méthode par insertion. Je les tris par ordre croissant.
 
J'ai compris le principe de cette méthode :
 
l'utilisateur rempli le tableau
on trouve le plus petit
on le met à la première place
ensuite on réduit la taille du tableau de "1"
on trouve le plus petit nombre et on le met a la première place de la nouvelle taille.  
Ainsi de suite jusqu'au dernier.
 
Voila ce que j'ai fait cependant je ne vois pas comment réduit la taille du tableau au fur et à mesure que "j'avance" dans le tableau. Faut-il faire une boucle dans la boucle? J'aurais tendance à penser ça mais je ne suis pas sûr. merci de m'aider.
 

Code :
  1. /* déclaration des fichiers nécessaires*/
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. int tab[10];
  5. int compteur;
  6. int i,nb,nb2,taille;
  7. int main()
  8. {
  9. /*  insertion des valeurs dans le tableau */
  10. for (compteur=1;compteur<11;compteur++)
  11. {
  12.     printf("Saisissez la valeur numero %d : ", compteur);
  13.     scanf("%d",&tab[compteur]);
  14. }
  15. /* tri des données*/
  16. for (i=1;i=10;i++)
  17. {
  18.     nb=tab[i];
  19.     if (tab[i]<nb)
  20.     {    nb=tab[i];
  21.         nb2=nb;
  22.         tab[i]=nb;
  23.     }
  24.     tab[i]=tab[i]+1;
  25. }
  26. /* affichage du contenu du tableau  */
  27. for (compteur=1;compteur<11;compteur++)
  28. {
  29.     printf("%d,%d",compteur,tab[compteur]);
  30. }
  31. }



 
Première chose : tu déclares int tab[10], donc tu pourras utiliser tab[0] à tab[9] => revoir la condition ligne 13
De plus, tu gagnerais à faire un #define MAX 10 et à utiliser MAX à chaque fois, ce qui te permet de le changer en une seule fois.
 
Enfin, tu gagnerais à séparer ton programme en fonctions :
- acquisition des valeurs
- tri
- affichage
 
Ta fonction main devient :
 

Code :
  1. int main(){
  2.   int tab[MAX];
  3.   int tab_trie[MAX];
  4.  
  5.   acquisition(tab);
  6.   tri(tab, tab_trie);
  7.   affichage(tab_trie);
  8. }


 
Pour l'acquisition et l'affichage, tu gardes le même code
Pour le tri

Code :
  1. void tri(int tab[], int tab_trie[]){
  2.   int length, i, min;
  3.   for(length=MAX;length>0;length--){
  4.     min = 32000; // Tu mets ici la valeur maximale !
  5.     for(i=0;i<length;i++){
  6.       if(tab[i]<min){
  7.         min=tab[i];
  8.       }
  9.     }
  10.     tab_trie[MAX-length]=min;
  11.   }
  12. }


Ca fait un moment que j'ai pas fait de C, mais ça devrait marcher ...
 
En fait tu es obligé de passer par un deuxième tableau (au moins temporairement dans ta fonction de tri) pour ne pas écraser les valeurs à trier.

n°1750400
dap++
Script kiddie
Posté le 23-06-2008 à 22:35:34  profilanswer
 

Là j'ai comme un doute : je suis le seul à utiliser le tri par insertion et en ajoutant les éléments un par un au fur et à mesure qu'ils arrivent ?  :??:
Sinon on n'est pas obligé d'utiliser un deuxième tableau si on trie d'un coup, il suffit de séparer le tableau en deux parties : la première qui est déjà triée (elle contient un seul élément au départ) et la deuxième qui contient le reste.

Code :
  1. #include <stdio.h>
  2. #define  MAX  10
  3. static void tri (int tab[], size_t taille);
  4. int main (void)
  5. {
  6.   int tab[MAX];
  7.   unsigned int i;
  8.  
  9.   /* initialisation du tableau avec des valeurs bidon */
  10.   for (i = 0; i < MAX; ++i)
  11.   {
  12.    tab[i] = MAX - i;
  13.   }
  14.   tri(tab, MAX);
  15.  
  16.   for (i = 0; i < MAX; ++i)
  17.   {
  18.     printf("%d\n", tab[i]);
  19.   }
  20.  
  21.   return 0;
  22. }
  23. static void tri (int tab[], size_t taille)
  24. {
  25.   size_t i;
  26.   int j;
  27.   int temp;
  28.   /* iteration sur la section non triee */
  29.   for (i = 1; i < taille; ++i)
  30.   {
  31.     /* element a inserer dans la section triee */
  32.     temp = tab[i];
  33.     /* avant-dernier element de la section triee */
  34.     j = i - 1;
  35.    
  36.     while (j >= 0 && tab[j] > temp)
  37.     {
  38.       tab[j+1] = tab[j];
  39.       --j;
  40.     }
  41.     tab[j+1] = temp;
  42.   }
  43. }


---------------
dap.developpez.com
n°1750549
Paulp
~, sweet ~
Posté le 24-06-2008 à 11:20:04  profilanswer
 

dap++ a écrit :

Là j'ai comme un doute : je suis le seul à utiliser le tri par insertion et en ajoutant les éléments un par un au fur et à mesure qu'ils arrivent ?  :??:
Sinon on n'est pas obligé d'utiliser un deuxième tableau si on trie d'un coup, il suffit de séparer le tableau en deux parties : la première qui est déjà triée (elle contient un seul élément au départ) et la deuxième qui contient le reste.

Code :
  1. #include <stdio.h>
  2. #define  MAX  10
  3. static void tri (int tab[], size_t taille);
  4. int main (void)
  5. {
  6.   int tab[MAX];
  7.   unsigned int i;
  8.  
  9.   /* initialisation du tableau avec des valeurs bidon */
  10.   for (i = 0; i < MAX; ++i)
  11.   {
  12.    tab[i] = MAX - i;
  13.   }
  14.   tri(tab, MAX);
  15.  
  16.   for (i = 0; i < MAX; ++i)
  17.   {
  18.     printf("%d\n", tab[i]);
  19.   }
  20.  
  21.   return 0;
  22. }
  23. static void tri (int tab[], size_t taille)
  24. {
  25.   size_t i;
  26.   int j;
  27.   int temp;
  28.   /* iteration sur la section non triee */
  29.   for (i = 1; i < taille; ++i)
  30.   {
  31.     /* element a inserer dans la section triee */
  32.     temp = tab[i];
  33.     /* avant-dernier element de la section triee */
  34.     j = i - 1;
  35.    
  36.     while (j >= 0 && tab[j] > temp)
  37.     {
  38.       tab[j+1] = tab[j];
  39.       --j;
  40.     }
  41.     tab[j+1] = temp;
  42.   }
  43. }



Ma version évite les insertions qui sont assez couteuses dans les tableaux. Je pense qu'elle est plus efficace en terme de complexité
A noter qu'on peut ajouter à ta méthode (enfin, pas pour MAX = 10, ce serait assez con) une recherche dichotomique pour la place de l'élément à insérer.
On peut aussi dans ma méthode afficher les éléments au fur et à mesure où ils sont triés, ça évite une boucle.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  Tri par insertion

 

Sujets relatifs
requete insertion en vbProblème d'insertion dans une table sous ACCESS
insertion automatique de champs dans une tableFonction de calcul de stock par ordre d'insertion
Gros pb d'insertion d'un IzzyMenu CSS dans htmlAccess et insertion de sous formulaires dynamiques
Tri par insertion ...[C] Tri par insertion simple & pointeurs
Tri par insertion -> Adaptation pour chaine de car[C] Tri par insertion
Plus de sujets relatifs à : Tri par insertion


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR