Accueil de Gladir.com Notes légales de Gladir.com Flux RSS des nouvelles du site Gladir.com - Langage de programmation - C - Tri & Théorie des ordres - Tri Shell-Metzner Section du logiciel DOS «MonsterBook» Inventaire de la bibliothèque de Gladir.com Entrée administrateur

La technique de tri nommée «Shell-Metzner», est en fait une technique de réduction du nombre de comparaison a effectuer pour trier un tableau. Comment si prend-on? C'est simple, la comparaison s'effectue entre 2 éléments séparé par un écart égal (au départ) à la moitié de la taille du tableau. Ensuite, la comparaison s'effectue entre des éléments séparées par un écart égal au nombre d'élément du tableau divisée par 4. Lorsque l'écart atteint finalement 1, la tri est terminé. Vous trouverez la réponse que vous souhaitez, à l'aide du code source C suivant :

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MaxTableau 8
  5.  
  6. int main()
  7. {
  8.     int K,L,I,J,Inversion,ecart,Temporaire;
  9.     int Tableau[MaxTableau] = {15, 10, 23, 2, 8, 9, 14, 16};
  10.     printf("Avant:");
  11.  
  12.     for(K = 0; K < MaxTableau; K++) printf("%i, ",Tableau[K]);
  13.  
  14.     Inversion = 0;
  15.     ecart = MaxTableau;
  16.     do {
  17.         ecart >>= 1;
  18.         do {
  19.             Inversion = 0;
  20.             for(I = 0; I <= MaxTableau - ecart - 1; I++) {
  21.                 J = I + ecart;
  22.                 if(Tableau[J] < Tableau[I]) {
  23.                     Temporaire = Tableau[I];
  24.                     Tableau[I] = Tableau[J];
  25.                     Tableau[J] = Temporaire;
  26.                     Inversion = 1;
  27.                 }
  28.             }
  29.         } while (1 == Inversion);
  30.     } while (1 != ecart);
  31.  
  32.     printf("\nAprès:");
  33.     for(L = 0; L < MaxTableau; L++) {
  34.         printf(", %i",Tableau[L]);
  35.     }
  36.     printf("\n");
  37.     return 0;
  38. }

on obtiendra le résultat suivant :

Avant:15, 10, 23, 2, 8, 9, 14, 16,
Après:2, 8, 9, 10, 14, 15, 16, 23,

Voir également

Algorithme - Tri


Dernière mise à jour: Jeudi, le 22 avril 2011