Articles avec le tag ‘array’

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 !

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