Tri récursif d'une liste numé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 numérique en JavaScript
» chaînes et tableaux en JavaScript | » Cas alphanumérique

L'instruction de tri L.sort(), List sort : trier Liste, existe en JavaScript mais notre objectif est de la réécrire au moyen d'une procédure récursive dans le cas de valeurs numé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], les ei sont des chaînes de caractères, comme par exemple "chat", "rose blanche", mais aussi "100". Et là est le petit problème car le langage use de l'ordre lexicographique, celui du dictionnaire. En ce sens 100, commençant par 1 est inférieur à 7 !

Nous allons adapter ici le programme décrit dans le cas d'un tri alphanumérique. Le principe récursif de ce tri est simple :

Si la liste de nombres ne possède qu'un seul élément α, alors la liste triée est [α] (condition d'arrêt).
Sinon, la liste triée sera obtenue en adjoignant (concaténation à droite, notée + ci-dessous) le plus petit élément de la liste qui reste à trier à la liste triée en cours de formation. On peut résumer ainsi l'algorithme :

Tri[L_n] = Min(L_n) + Tri[L_n-1]

➔ 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 = [9,3,2,5] 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 2; on le place en première position;
L_tri devient [2,9,3,5] et lg = 3. Reste à trier L = [9,3,5];
le minimum est 3 en 2è position. L_tri devient [2,3,9,5] et lg = 2. Reste à trier L = [9,5];
le minimum est 5 en 2è position. L_tri devient [2,3,5,9] et lg = 1. Reste à trier L = [9];
le minimum est 9 ! L_tri devient [2,3,5,9] et lg = 0. Le tri est terminé.

! Petit souci : comme évoqué en préambule, en tant qu'élément d'une liste, 100 sera considéré comme une chaîne de caractères et par conséquent 100 < 7 (ordre lexicographique). Il faut donc récupérer la valeur numérique des éléments de la liste. Mais JavaScript est capricieux et refuse de considérer comme numérique les eval(L.slice(0,1)) et eval(L.slice(i,i+1)). On rajoute alors un join() qui convertit les L.slice en chaînes de caractères dont on peut récupérer la valeur numérique. Par ailleurs, l'instruction L = L.split(car) retourne dans L la liste des mots séparés par car (une virgule par exemple).

» fonctions join , split , concat , slice , splice

<SCRIPT LANGUAGE=JavaScript>
var lg=1
function va_trier()
{
L=[100,7,-8,20,3,1]
L=prompt("Donnez votre liste en séparant par des virgules :",L)
L=L.split(",")
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); // M est la liste [min,idx] qui reste à trier obtenue dans Min()
list_tri=list_tri.concat(M[0]); // équivaut à list_tri = M[0]+list_tri
/
L.slice(M[1],1);lg--;
trier(L)
}
}

function Min(L)           // recherche de l'élément minimal
{
min=eval(L.slice(0,1).join());
idx=0
for(i=0;i<lg;i++)
{
e=eval(L.slice(i,i+1).join())
if(e<min){min=e,idx=i}
}
return [min,idx]
// on retourne le minimum et son index (rang dans la liste)
}
</SCRIPT>