Javascript dans sa forme actuelle ne convient pas pour les algorithmes évolués, notamment il ne faut pas perdre de vue habituellement les tableaux dans une page web sont de faibles importances, et dans ce cas les évaluations mathématiques habituellement asymptotiques en O(n) ne sont pas appropriées.
tri par sélection :
C'est le tri le plus simple, on effectue une double boucle. Une externe toujours triée et une interne. La boucle externe de 0 à i-1 est triée : c'est "l'invariant" de l'algorithme. Dans la boucle interne, on cherche le maximum(minimum) du sous tableau de i à la fin du tableau.
Pour cela, on pose comme hypothèse, qu'en i se trouve le maximum (minimum) du sous tableau, et on parcours ce sous-tableau de i+1 jusqu'à la fin en comparant chaque élément avec l'élément en i, et éventuellement on permute deux éléments lorsque la comparaison contredit notre hypothèse.
Quand on a parcouru tout le sous tableau interne, on est certain qu'en i se trouve le maximum(minimum) du sous tableau de i à la fin du tableau.
On peut alors recommencer à chercher le prochain maximum du sous tableau interne de mais cette fois i+1 à la fin du tableau.
On peut utiliser f, une "fonction de valuation" qui renvoie true ou false suivant que les valeurs à comparer sont plus grandes ou plus petites. (une fonction est une variable en javascript)
// notre fonction de valuation f renvoie true ou false:
var f = function(a,b){
return a>b ;
}
function tri(l,f){
for(var i= 0 ; i< l.length; i++){
// le tableau est trié de 0 à i-1
// La boucle interne recherche le maximum
// de i+1 à la fin du tableau.
for(var j=i+1; j< l.length; j++){
if(f( l[j], l[i]) ){
var temp = l[j];
l[j]=l[i];
l[i]=temp;
}
}
}
return l ;
}
tri([1,4,3,7],function(a,b){ return a>b ;});
Note sur la fonction swap:
Firefox permet de swapper (permuter) ainsi:
[l[i] ,l[j]] = [l[j],l[i]] ;// swapper.
Mais pas IE!!
Le tri par insertion
Dans ce tri, une première boucle parcourt le tableau de gauche à droite, tous les éléments à gauche du tableau sont triés. Une deuxième boucle insère dans le tableaux de gauche les éléments, de la même manière qu'un joueur de cartes insère une nouvelle carte dans un jeux trié de gauche à droite. En décalant les autres cartes vers la droite pour insérer la carte courante au bon endroit.
Une autre image, plus simple est celle d'une rangée de livre sur une étagère, on considère que le premier livre à gauche est en place, si le deuxième livre est en place, on passe au 3ème, sinon on décale à gauche le premier livre pour insérer en première position le livre que l'on a en main et ainsi de suite...
L'"invariant" est que la partie gauche du tableau est toujours triée.
var tri_insert = function(t , f){
for(var i=1 ; i < t.length ; i++){
var temp= t[i] ;
var j = i-1 ;
while( f(temp, t[j]) && j>=0){
t[j+1]= t[j]
j-- ;
};
t[j+1]=temp ;
}
return t;
}
tri_insert([5,3,6,2,1] , function(a, b){ return a < b;})
Ce tri est probablement l'un des plus simple et efficace, sa vitesse d'exécution est en général proportionnelle au carré de la taille du tableau (on peut noter O(n2). Mais, si le tableau est trié, le tri s'effectue dans un temps proportionnel à la longueur du tableau. Si le tableau est trié en sens inverse, c'est le cas le pire, le tri s'effectue en un temps proportionnel au carré de la longueur du tableau.
Tri fusion en javascript
Nous avons vu créé naïvement deux tris, qui s'effectuent habituellement, en un temps proportionnel au carré de la taille du tableau. Comment faire plus rapide ?
Si notre tableau contient n éléments on peut aller beaucoup plus vite et effectuer ce tri à une vitesse de nlog(n), il existe de nombreuses variantes de tris. On va voir ici le tri-fusion.
Le tri-fusion utilise le paradigme de Machiavel : "diviser pour régner" , "divide and conquer", ou encore plus modestement fait appel au couple division-récursion.
Maintenant accrochez vous : faire un tri fusion en javascript :
- Une première fonction "divise" divise votre tableau en 2 tableaux.
- Une deuxième fonction "fusion" fusionne deux tableaux en un seul tableau, mais en choisissant entre les deux derniers (ou premiers) éléments de chaque tableau celui qui est le plus petit (ou plus grand).
A l'image d'un professeur qui distribue les copies à partir de deux tas de copies placées devant lui. Il ne voit que la dernière copie de chaque tas, choisit entre deux copies celle dont la note est la plus forte (ou faible).
- Enfin l'étape finale est de faire cela récursivement:
- On divise en deux chaque tableau, sauf si sa taille est inférieur ou égale à 1
- On tri chacun des deux sous tableaux.
- Enfin, on fusionne les deux tableaux triés que l'on renvoi en résultat.
//Tri fusion sur liste:
function tri_fusion(liste){
var divise= function(l){
if(l.length === 0) return [[],[]] ;
if(l.length ===1 ) return [ l , []] ;
var last = l.pop();
var lastlast = l.pop();
var [g,d]= divise(l) ;
g.push(last) ; d.push(lastlast) ;
return [g,d];
}
//divise([1,3,4,6]); //[[3, 6], [1, 4]]
///// Attention aux tableaux de tableaux:
var fusion = function(a,b){
if(a.length===0 && b.length===0) return [] ;
if(a.length===0) return b;
if(b.length===0) return a;
var [p,q]= [a.pop(),b.pop()];
if(p < q){
b.push(q);
var temp= fusion(a,b);
temp.push(p);
return temp;
}else{
a.push(p);
var temp= fusion(a,b);
temp.push(q);
return temp ;}
}
//fusion([3], [5]); //
var tri = function(l){
if(l.length <=1 ) return l ;
var [g,d] = divise(l) ;
return fusion (tri(g),tri(d));
}
//tri(liste);
}//tri([2,3,5,0,10,10,9]);
function m(n){
var r=new Array(n);
for(var i=0; i< n;i++)
r[i] = Math.round(Math.random()*1000000) ;
return r;
}
tri_fusion(m(10000)); // too much recursion !
On le voit que le tri fusion n'est pas adapté à la structure actuelle, du javascript, qui est un langage interprété par un autre langage et qui ne convient pas au contexte habituel des pages web.
C'est cependant un tri efficace qu'il faut connaître.
Il existe des tas d'autres algorithmes de tri en O(n log n), l'autre très connu est le tri-rapide ou "quick-sort" qui s'effectue plus dans un contexte de tableau que de liste.
Simplifions nous la vie: la fonction sort
En pratique, il est plus simple d'utiliser la fonction "sort" déjà présente dans javascript: Array.sort.
Il est ainsi possible de trier une liste en lui appliquant la méthode sort(f). Cette méthode prend en argument, une fonction de valuation elle même à deux arguments qui retourne un résultat positif ou négatif suivant la façon dont vous voulez trier.
Par exemple :
- var mafonction= fonction(a,b){ return a-b ;};
- montableau.sort(mafonction) ;
N'oubliez pas qu'une fonction en javascript est un type au même titre qu'une string...
var liste=[4,5,9,0,1];
// on donne en argument une fonction anonyme:
liste.sort(function(a,b){ return a-b } ); //[0, 1, 4, 5, 9]
liste.sort(function(a,b){ return b-a } ); //[9, 5, 4, 1, 0]
// Trier en ordre alphabétique...
var liste=['i',' ','l','o','v','e',' ', 'y','o','u'];
liste.sort(function(a,b){ return a.charCodeAt(0)- b.charCodeAt(0) } );
//[" ", " ", "e", "i", "l", "o", "o", "u", "v", "y"]
//Pour tout mélanger on lui donne Math.random !!
liste.sort(function(a,b){ return Math.random()-0.5 } );//[4, 0, 5, 9, 1]
Ainsi, en pratique on utilisera sort et une fonction de valuation à deux arguments qui permettra un tri parfait, voire de mélanger tout comme ci dessus avec notre fonction
anonyme retournant un nombre aléatoire entre -0.5 et + 0.5.
