Algorithme de tri rapide et stable implémenté en JavaScript

Question

Je cherche à trier un tableau d'environ 200 à 300 objets, en triant sur une clé spécifique et dans un ordre donné (asc/desc). L'ordre des résultats doit être cohérent et stable.

Quel serait le meilleur algorithme à utiliser, et pourriez-vous fournir un exemple de son implémentation en javascript?

Merci!

Answer 1

Il est possible d'obtenir un tri stable à partir d'une fonction de tri non stable.

Avant de trier, vous obtenez la position de tous les éléments. Dans votre condition de tri, si les deux éléments sont égaux, alors vous triez par la position.

Tada! Vous avez un tri stable.

J'ai écrit un article à ce sujet sur mon blog si vous voulez en savoir plus sur cette technique et comment l'implémenter: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html

Answer 2

Comme vous recherchez quelque chose de stable, le tri fusion devrait faire l'affaire.

http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

Le code peut être trouvé sur le site web ci-dessus:

function mergeSort(arr)
{
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

EDIT:

According to this post, it looks like Array.Sort in some implementations uses a merge sort.

Answer 3

Je sais que cette question a été répondue depuis un certain temps, mais j'ai une bonne implémentation stable de merge sort pour Array et jQuery dans mon presse-papiers, donc je vais la partager dans l'espoir que certains futurs chercheurs pourraient la trouver utile.

Cela vous permet de spécifier votre propre fonction de comparaison tout comme l'implémentation normale Array.sort.

Implémentation

// Ajouter un merge sort stable aux prototypes Array et jQuery
// Remarque : Nous l'encapsulons dans une fermeture pour ne pas polluer le global
//        namespace, mais nous ne l'insérons pas dans $(document).ready, car il n'est
//        pas dépendant du DOM
(function() {

  // exposer à Array et jQuery
  Array.prototype.mergeSort = jQuery.fn.mergeSort = mergeSort;

  function mergeSort(compare) {

    var length = this.length,
        middle = Math.floor(length / 2);

    if (!compare) {
      compare = function(left, right) {
        if (left < right)
          return -1;
        if (left == right)
          return 0;
        else
          return 1;
      };
    }

    if (length < 2)
      return this;

    return merge(
      this.slice(0, middle).mergeSort(compare),
      this.slice(middle, length).mergeSort(compare),
      compare
    );
  }

  function merge(left, right, compare) {

    var result = [];

    while (left.length > 0 || right.length > 0) {
      if (left.length > 0 && right.length > 0) {
        if (compare(left[0], right[0]) <= 0) {
          result.push(left[0]);
          left = left.slice(1);
        }
        else {
          result.push(right[0]);
          right = right.slice(1);
        }
      }
      else if (left.length > 0) {
        result.push(left[0]);
        left = left.slice(1);
      }
      else if (right.length > 0) {
        result.push(right[0]);
        right = right.slice(1);
      }
    }
    return result;
  }
})();

Exemple d'utilisation

var sorted = [
  'Finger',
  'Sandwich',
  'sandwich',
  '5 pork rinds',
  'a guy named Steve',
  'some noodles',
  'mops and brooms',
  'Potato Chip Brand® chips'
].mergeSort(function(left, right) {
  lval = left.toLowerCase();
  rval = right.toLowerCase();

  console.log(lval, rval);
  if (lval < rval)
    return -1;
  else if (lval == rval)
    return 0;
  else
    return 1;
});

sorted == ["5 pork rinds", "a guy named Steve", "Finger", "mops and brooms", "Potato Chip Brand® chips", "Sandwich", "sandwich", "some noodles"];

Answer 4

Voici une implémentation stable. Cela fonctionne en utilisant le tri natif, mais dans les cas où les éléments se comparent également, vous cassez les liens en utilisant la position d'index d'origine.

function stableSort(arr, cmpFunc) {
    //wrap the arr elements in wrapper objects, so we can associate them with their origional starting index position
    var arrOfWrapper = arr.map(function(elem, idx){
        return {elem: elem, idx: idx};
    });

    //sort the wrappers, breaking sorting ties by using their elements orig index position
    arrOfWrapper.sort(function(wrapperA, wrapperB){
        var cmpDiff = cmpFunc(wrapperA.elem, wrapperB.elem);
        return cmpDiff === 0 
             ? wrapperA.idx - wrapperB.idx
             : cmpDiff;
    });

    //unwrap and return the elements
    return arrOfWrapper.map(function(wrapper){
        return wrapper.elem;
    });
}

un test non exhaustif

var res = stableSort([{a:1, b:4}, {a:1, b:5}], function(a, b){
    return a.a - b.a;
});
console.log(res);

une autre réponse a fait allusion à cela, mais n'a pas posté le code.

mais, ce n'est pas rapide selon mon benchmark. J'ai modifié une implémentation de tri fusion pour accepter une fonction de comparaison personnalisée, et c'était beaucoup plus rapide.

Answer 5

Le tri par dénombrement est plus rapide que le tri fusion (il s'effectue en temps O(n)) et il est destiné à être utilisé sur des entiers.

Math.counting_sort = function (m) {
    var i
    var j
    var k
    var step
    var start
    var Output
    var hash
    k = m.length
    Output = new Array ()
    hash = new Array ()
    // commencer à la valeur la plus basse possible de m
    start = 0
    step = 1
    // hasher toutes les valeurs
    i = 0
    while ( i < k ) {
        var _m = m[i]
        hash [_m] = _m
        i = i + 1
    }
    i = 0
    j = start
    // trouver tous les éléments dans x
    while ( i < k ) {
        while ( j != hash[j] ) {
            j = j + step
        }
        Output [i] = j
        i = i + 1
        j = j + step
    }
    return Output
}

Exemple:

var uArray = new Array ()
var sArray = new Array ()
uArray = [ 10,1,9,2,8,3,7,4,6,5 ]
sArray = Math.counting_sort ( uArray ) // retourne un tableau trié