Section courante

A propos

Section administrative du site

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 Perl suivant :

  1. #!/usr/bin/perl
  2.  
  3. use strict;
  4. use warnings;
  5.  
  6. my @Tableau = (
  7.  15, 10, 23, 2, 8, 9, 14, 16
  8. );
  9.  
  10. print "Avant:";
  11. for(my $K = 0; $K < ($#Tableau+1); $K++) {
  12.  print $Tableau[$K].", ";
  13. }
  14.  
  15. my $Inversion = 0;
  16. my $ecart = ($#Tableau + 1);
  17. do {
  18.   $ecart /= 2;
  19.   do {
  20.      $Inversion = 0;
  21.      for(my $I = 0; $I <= ($#Tableau + 1) - $ecart - 1; $I++) {
  22.      my $J = $I + $ecart;
  23.      if($Tableau[$J] < $Tableau[$I]) {
  24.         my $Temporaire = $Tableau[$I];
  25.         $Tableau[$I] = $Tableau[$J];
  26.         $Tableau[$J] = $Temporaire;
  27.         $Inversion = 1;
  28.      }
  29.      }
  30.   } until (1 != $Inversion);
  31. } until (1 == $ecart);
  32.  
  33. print "\nAprès:";
  34. for(my $L = 0; $L < ($#Tableau + 1); $L++) {
  35.   print $Tableau[$L].", ";
  36. }
  37. print "\n";

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 17 janvier 2019