Articles avec le tag ‘tableau’

Algorithme de tri stable en javascript

Dans un esprit d’exhaustivité par rapport à l’article précédent, voici maintenant un algorithme qui, faute d’implémenter le tri rapide, effectue un tri stable (pour rappel, voir wikipédia) en se basant sur la fonction de tri native de javascript.

L’implémentation sous-jacente dépendra donc de l’environnement d’exécution (c’est à dire du navigateur dans la plupart des cas) mais elle est probablement suffisante pour la plupart des usages.

/**
* Sort the provided array, in the specified order, on the value returned by the callback.
* This is a stable-sorting algorithm implementation, ie. two call with the same array will
* return the same results orders, especially with equal values.
*
* @param array {Array} the array to sort
* @param order {string} 'ASC' or 'DESC'
* @param getValue {function} the callback which will return the value on which the sort will occurs
* @returns {Array}
*/
function stableSort(array, order, getValue) {
 
    // prepare sorting
    var keys_order = [];
    var result = []
    for (var i=0; i<array .length; i++) {
        keys_order[array[i]] = i;
        result.push(array[i]);
    }
 
    // callback for javascript native Array.sort()
    var sort_fc = function (a, b) {
        var val_a = getValue(a);
        var val_b = getValue(b);
        if (val_a === val_b)
            return keys_order[a] - keys_order[b];
 
        if (val_a < val_b) {
            if (order == 'ASC') return -1;
            else return 1;
        }
        else {
            if (order == 'ASC') return 1;
            else return -1;
        }
    };
 
    result.sort(sort_fc);
    return result;
}

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 obj7 = {name:"edmond", age:17};
 
var my_array = [obj1, obj2, obj3, obj4, obj5, obj6, obj7];
 
var getAge = function(person) {
     return person.age;
}
 
var sorted_array = stableSort(my_array, 'ASC', getAge);

Ici la variable my_array ne sera pas modifiée. Le résultat du tri sera plutôt retournée en sortie de la fonction, mais il est simple de modifier ce comportement.

Au final, sorted_array ressemblera à ça :

console.log(sorted_array);
// [obj5, obj4, obj6, obj7, obj1, obj2, obj3]
// ... age:6 ... age:12 ... age:17 ... age:17 ... age:22 ... age:47 ... age:63 ...
// ... henri ... sasha  ... paul   ... edmond ... bob    ... john   ... william ...

Remarquez que l’ordre relatif entre paul et edmond (dont les âges sont égaux) est resté le même en sortie de la fonction de tri : c’est un tri stable !

Rechercher
Catégories
Récemment écouté
This Charming Man
The Smiths
The Sound Of The Smiths [Deluxe Edition]
Il y a 2 jours
Reptilia
The Strokes
Room on Fire
Il y a 2 jours
Light My Fire
The Doors
The Doors
Il y a 2 jours
You Really Got Me (Remastered)
The Kinks
The Anthology 1964 - 1971
Il y a 2 jours
Walk of Life
Dire Straits
Brothers in Arms
Il y a 2 jours