Tri par insertion

Tri par insertion - C - Programmation

Marsh Posté le 23-06-2008 à 18:10:34    

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>
  5. int tab[10];
  6. int compteur;
  7. int i,nb,nb2,taille;
  9. int main()
  11. {
  12. /*  insertion des valeurs dans le tableau */
  13. for (compteur=1;compteur<11;compteur++)
  14. {
  15.     printf("Saisissez la valeur numero %d : ", compteur);
  16.     scanf("%d",&tab[compteur]);
  18. }
  19. /* tri des données*/
  21. for (i=1;i=10;i++)
  24. {
  25.     nb=tab[i];
  26.     if (tab[i]<nb)
  27.     {    nb=tab[i];
  28.         nb2=nb;
  29.         tab[i]=nb;
  30.     }
  31.     tab[i]=tab[i]+1;
  32. }
  33. /* affichage du contenu du tableau  */
  34. for (compteur=1;compteur<11;compteur++)
  35. {
  36.     printf("%d,%d",compteur,tab[compteur]);
  38. }
  39. }

Message cité 1 fois
Message édité par slr56 le 23-06-2008 à 18:12:34
Reply

Marsh Posté le 23-06-2008 à 18:10:34   

Reply

Marsh Posté le 23-06-2008 à 18:31:16    

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

Reply

Marsh Posté le 23-06-2008 à 18:33:32    

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>
  5. int tab[10];
  6. int compteur;
  7. int i,nb,nb2,taille;
  9. int main()
  11. {
  12. /*  insertion des valeurs dans le tableau */
  13. for (compteur=1;compteur<11;compteur++)
  14. {
  15.     printf("Saisissez la valeur numero %d : ", compteur);
  16.     scanf("%d",&tab[compteur]);
  18. }
  19. /* tri des données*/
  21. for (i=1;i=10;i++)
  24. {
  25.     nb=tab[i];
  26.     if (tab[i]<nb)
  27.     {    nb=tab[i];
  28.         nb2=nb;
  29.         tab[i]=nb;
  30.     }
  31.     tab[i]=tab[i]+1;
  32. }
  33. /* affichage du contenu du tableau  */
  34. for (compteur=1;compteur<11;compteur++)
  35. {
  36.     printf("%d,%d",compteur,tab[compteur]);
  38. }
  39. }



 
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.

Reply

Marsh Posté le 23-06-2008 à 22:35:34    

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

Message cité 1 fois

---------------
dap.developpez.com
Reply

Marsh Posté le 24-06-2008 à 11:20:04    

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



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.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed