Tri récursif d'une liste alphanumérique

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

Un programme récursif de tri alphanumérique en JavaScript
» Chaînes et tableaux en JavaScript | » Cas numérique

L'instruction de tri L.sort(), List sort : trier Liste, existe en JavaScript mais l'objectif est ici de la réécrire au moyen d'une procédure récursive dans le cas de valeurs alphanumériques. Dans le langage JavaScript, une liste (tableau à 1 dimension) de n éléments est un n-uplet noté [e₀,e₁,e₂,...,e_n-1]. Le principe récursif de ce tri est simple :

Si la liste ne possède qu'un seul élément a, alors la liste triée est [a] (condition d'arrêt).
Sinon, la liste triée sera obtenue en adjoignant (concaténation à droite) le plus petit élément de la liste qui reste à trier à la liste triée en cours de formation.

➔ Si à une étape intermédiaire, la liste s'avère triée, le programme ne s'en aperçoit pas : chaque élément reste à sa place. Le lecteur intéressé pourra sans difficultés améliorer le programme par un test consistant à vérifier que le plus petit élément est le premier.

La condition d'arrêt est gérée par l'instruction while(lg>0) : lg désignant la longueur de la liste qui reste à trier. Si lg = 0, le tri est terminé.

Soit à trier alphabétiquement la liste L = [d,b,a,c] en la liste L_tri. On a lg = 4

L n'est pas triée; son plus petit élément Min(L) est recherché : c'est a;
L_tri devient [a,d,a,c] et lg = 3. Reste à trier L = [d,b,c];
le minimum est b en 2è position. L_tri devient [a,b,d,c] et lg = 2. Reste à trier L = [d,c];
le minimum est c en 2è position. L_tri devient [a,b,c,d] et lg = 1. Reste à trier L = [d];
le minimum est d ! L_tri devient [a,b,c,d] et lg = 0. Le tri est terminé.

» fonctions join , split , concat , slice , splice

➔ Par défaut, à titre d'exemple, le programme trie la liste L = [souris, chat, rat, chien, mulot, araignée, papillon]. Dans le cas d'une liste de nombres, le tri ne va pas donner le résultat escompté : un nombre comme 100 sera considéré comme une chaîne de caractères et par conséquent 100 < 7 (ordre lexicographique). Mais on peut remédier facilement à ce petit souci :

Adaptation de l'algorithme au cas purement numérique : »

<SCRIPT LANGUAGE=JavaScript>
var lg,L=new Array()
function va_trier()
{
L=["souris","chat","rat","chien","mulot","araignée","papillon"]
L=prompt("Donnez votre liste en séparant par des virgules :",L)
L=L.split(","); // retourne dans L la liste des mots séparés par une virgule
lg=1;list_tri=[ ] // liste triée, vide au départ
trier(L);alert(list_tri)
}

function trier(L) //fonction récursive de tri
{
while(lg>0)
{
lg=L.length;

M=Min(L); // recherche de l'élément minimal
list_tri=M[0]+list_tri; // équivaut à list_tri = list_tri.concat(M[0]);
L.splice(M[1],1); // ôte M[1] de la liste L
lg--;
trier(L)
}
}

function Min(L)
{
min=L.slice(0,1); // initialisation : min est la liste égale au 1er élément de L
idx=0;
for(i=0;i<lg;i++)
{
e=L.slice(i,i+1)
if(e<min){min=e,idx=i}
}
return [min,idx] // M est la liste [min,idx] : on retourne le minimum et son rang dans la liste
}
</SCRIPT>