Articles avec le tag ‘tri rapide’

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

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