Tri JavaScript d'une liste par insertion

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

Sans faire appel à la fonction intégrée L.sort du langage JavaScript, une réponse facilement programmable est la suivante : on passe en revue tous les éléments x₁, x₂, ..., x_n (dans cet exemple n = 7).

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.

! Le programme ci-dessous trie correctement toute série de nombres. Il prévoit de s'appliquer à des chaînes de caractères alphanumériques. Dans ce dernier cas, JavaScript utilise l'ordre lexicographique (celui du dictionnaire) mais on peut avoir des surprises car dans ce cas, par exemple, 100, commençant par 1, est "rangé" avant 7...

Passons en revue chaque élément x_i de la liste du second au n-ème en le comparant à tous ceux dont le rang est inférieur :

i = 2, x₂ initial = 6	rangs 2 comparé à rang1, pas d'échange :
i = 3, x₃ initial = 3	rang 3 comparé aux rangs 2 et 1 : 3 < 6 et 3 < 5. Le 3 saute entre le 5 et le 6 puis s'insère devant le 5.
i = 4, x₄ initial = 1	rang 4 comparé aux rangs 3, 2 et 1 : 1 < 6 et 1 < 5 et 1<3. Le 1 saute entre le 5 et le 6 puis entre le 3 et le 5 et s'insère finalement devant le 3.
i = 5	Le 2 prend place entre le 1 et le 3.
i = 6	Le 7 este à sa place.
i = 7	Le 4 prend place entre le 3 et le 5.

<SCRIPT LANGUAGE=JavaScript>
var x=new Array()
function tri_inser() // tri par insertion
{
n="";lexico="" // entrée des données (nombres ou chaines de caractères)
n=prompt("Vous n'entrerez que des nombres (o/n)? :",n)
if (n==null) {return}
if(n=="o"){num=1} else {num=0;lexico=" (ordre lexicographique)"}
n="";
n=eval(prompt("Entrez le nombre d'éléments de votre série :",n))
if (n==null) {return}
for(i=1;i<=n;i++) // entrée des valeurs
{
a="";a=prompt("Entrez x("+i+"):",a)
if (a==null) {return} else {if(num==0){x[i]=a} else {x[i]=eval(a)}};
}
alert("Votre liste : "+x.slice(1)) // l'index des données variant de 1 à n, on n'affiche pas x[0]
//qui vaut 0 par défaut puisque non défini » slice
for(i=2;i<=n;i++)
{
test=x[i];j=i // on teste la place de x[i] 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 l'élément testé s'avère inférieur aux précédents,
// on fait les sauts de puce arrière

x[j]=test
}
alert("Liste triée"+lexico+" :"+"\n"+x.slice(1))
}
</SCRIPT>