Algorithme de tri rapide en javascript

Voici une implémentation, en Javascript, de l’algorithme de tri rapide (Voir wikipédia) qui permet de trier n’importe quel tableau de variable JS, y compris des objets.

/**
* Swap to values at the specified indexes of the provided array
* @param array the array containing the values to swap
* @param idx1 the index (key) of the first value to swap
* @param idx2 the index (key) of the second value to swap
*/
function swap(array, idx1, idx2) {
    var tmp = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = tmp;
}
 
/**
* Method to quickly sort an array, according to the quicksort algorithm
* (see http://en.wikipedia.org/wiki/Quicksort)
* @param array the array to sort
* @param getValue {function} callback returning a number on which the comparison will occur
* @param begin index (key) of the first value to sort
* @param end index (key) of the last value to sort
*/
function quickSort(array, getValue, begin, end) {
     var left = begin-1;
     var right = end+1;
 
     var pivot = getValue(array[begin]);
 
     if (begin >= end) {
         return;
     }
 
     while(1) {
         do right--; while(getValue(array[right]) > pivot);
         do left++; while(getValue(array[left]) < pivot);
 
         if(left < right) {
              swap(array, left, right);
         }
         else break;
     }
 
     quickSort(array, getValue, begin, right);
     quickSort(array, getValue, right+1, end);
}

Et voici un exemple d’utilisation :

var obj1 = {name:"bob", age:22};
var obj2 = {name:"john", age:47};
var obj3 = {name:"william", age:63};
var obj4 = {name:"sasha", age:12};
var obj5 = {name:"henri", age:6};
var obj6 = {name:"paul", age:17};
 
var my_array = [obj1, obj2, obj3, obj4, obj5, obj6];
 
var getAge = function(person) {
     return person.age;
}
 
quickSort(my_array, getAge, 0, my_array.length-1);

Ceci modifiera la variable my_array qui aura, en sortie de la fonction, le contenu suivant :

console.log(my_array);
// [obj5, obj4, obj6, obj1, obj2, obj3]
// ... age:6 ... age:12 ... age:17 ... age:22 ... age:47 ... age:63 ...

Attention toutefois, cette implémentation n’est pas stable, cela signifie que les valeurs égales ne seront pas nécessairement triés dans le même ordre, à la sortie de la fonction, lorsque le même tableau est trié à plusieurs reprises.
Plus de détails sur la stabilité d’un tri : Voir wikipédia

Laisser un commentaire

Rechercher
Catégories
Récemment écouté
Gore Baby, Gore
Combichrist
Today We Are All Demons-Dark Side
Il y a 6 jours
Caliber:Death
Combichrist
Today We Are All Demons-Dark Side
Il y a 6 jours
427 FE
Combichrist
Today We Are All Demons-Dark Side
Il y a 6 jours
Machine Love
Combichrist
Today We Are All Demons-Dark Side
Il y a 6 jours
Till Death Do Us Party
Combichrist
Today We Are All Demons-Dark Side
Il y a 6 jours