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

L'instruction de tri L.sort(), List sort : trier Liste, existe en JavaScript mais notre objectif est de la réécrire !

Dans le langage JavaScript, une liste (tableau à 1 dimension) de n éléments est un n-uplet noté [e0,e1,e2,...,en-1]. Le principe récursif de ce tri est simple :

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

Par défaut, à titre d'exemple, le programme trie la liste L = [100,7,20,3,1]. L = Liste.split(car) : retourne dans L la liste des mots séparés par car (une virgule par exemple) dans la chaîne donnée Liste.

Dans le cas proposé, 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 force chaque L.slice en alphanumérique.

  fonctions  split , concat , slice

<SCRIPT LANGUAGE=JavaScript>
var lg=1
function va_trier()
{
L=[100,7,20,3,1]
L=prompt("Donnez votre liste :",L)   
// l'ordinateur affichera 100,7,20,3,1
L=L.split(",")   
 
list_tri=[ ]      
// liste triée, vide au départ
trier(L)
alert(list_tri)
}
// --------------------------------------------------------------------

function trier(L)            
   fonction de tri (récursive)         
{
while(lg>0)
{
lg=L.length;M=Min(L);list_tri=list_tri.concat(M[0]);    

// M est la liste [min,idx] qui reste à trier obtenue dans Min()

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>


© Serge Mehl - www.chronomath.com