ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Tri par insertion d'une suite de nombres

Si vous voulez trier ces jetons par ordre croissant, comment allez-vous faire sachant que les jetons ne peuvent faire que des sauts de puce successifs jeton par jeton ?

                 

Une réponse facilement programmable est la suivante :

  1. Les deux premiers éléments sont triés. Vous ne touchez donc pas au et au
     

  2. Le saute entre  et , puis devant le .

    Les 3 premiers éléments sont alors triés :

       |          

  1. Le saute entre   et , puis entre le   et le , puis devant le .

    Les 4 premiers éléments sont triés et on voit que le 7 est à sa place. On n'y touche pas :

              |   |    

  2. Le fait alors 4 sauts pour s'insérer entre 1 et 3 :

                |  

  1. Enfin, le 4 fait 3 sauts pour prendre sa place en s'insérant entre 3 et 5 :

                     

Cette méthode, très simple à programmer, consistant à insérer un élément à la bonne place, est celle que l'on utilise intuitivement pour classer des cartes, des fiches numérotées, des livres dans un rayon de bibliothèque. Dans ce dernier cas, il peut alors s'agir de l'ordre lexicographique (celui du dictionnaire) que JavaScript connaît fort bien. Le programme ci-dessous trie une série de nombres. Il est facilement adaptable à des chaînes de caractères alphanumériques.


<SCRIPT LANGUAGE=JavaScript>
var x=new Array()
function tri_inser()
{                                
// entrée des données
n="";x
n=eval(prompt("Entrez le nombre de valeurs de votre série de nombres :",n))
if (n==null) {return}
for(i=1;i<=n;i++)  
// entrée des valeurs (elles peuvent être des mots (chaines de caractères)
{
a="";a=prompt("Entrez x("+i+"):",a)
if (a==null) {return} else {x[i]=eval(a)};
}
alert("Votre liste : "+x.slice(1))        
// l'index variant de 1 à n, on n'affiche pas x[0] (qui vaut 0 par défaut)  slice


for(i=1;i<=n;i++)    
// programme tri par insertion
{
test=x[i];j=i              
// on teste la place de xi par rapport aux places j  précédemment triées (de i-1 à 1)
while(test<x[j-1] && j>=1) {x[j]=x[j-1];j--}  
// tant que le test est "positif" (xi inférieur aux précédents), on fait les sauts de puce
x[j]=test
}
alert("Liste triée : "+x.slice(1))
}
</SCRIPT>




© Serge Mehl - www.chronomath.com