Je cherche à trier un tableau d'environ 200 à 300 objets, en triant sur une clé spécifique et 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 donner un exemple de son implémentation en javascript?

Merci!

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, vous triez par position.

Tada! Vous avez une sorte stable.

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

Puisque vous recherchez quelque chose de stable, le tri par 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;
}

ÉDITER:

Selon cet article , cela ressemble à Array.Sort dans certaines implémentations utilise un tri par fusion.

Version un peu plus courte de la même chose utilisant des fonctionnalités ES2017 telles que les fonctions fléchées et la déstructuration:

Fonction

var stableSort = (arr, compare) => arr
  .map((item, index) => ({item, index}))
  .sort((a, b) => compare(a.item, b.item) || a.index - b.index)
  .map(({item}) => item)

Il accepte le tableau d'entrée et la fonction de comparaison:

stableSort([5,6,3,2,1], (a, b) => a - b)

Il retourne également un nouveau tableau au lieu de faire un tri sur place comme le Array.sort () intégré fonction intégrée.

Tester

Si nous prenons le inputtableau suivant , initialement trié par weight:

// sorted by weight
var input = [
  { height: 100, weight: 80 },
  { height: 90, weight: 90 },
  { height: 70, weight: 95 },
  { height: 100, weight: 100 },
  { height: 80, weight: 110 },
  { height: 110, weight: 115 },
  { height: 100, weight: 120 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 100, weight: 135 },
  { height: 75, weight: 140 },
  { height: 70, weight: 140 }
]

Puis triez-le en heightutilisant stableSort:

stableSort(input, (a, b) => a.height - b.height)

Résulte en:

// Items with the same height are still sorted by weight 
// which means they preserved their relative order.
var stable = [
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 70, weight: 140 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 80 },
  { height: 100, weight: 100 },
  { height: 100, weight: 120 },
  { height: 100, weight: 135 },
  { height: 110, weight: 115 }
]

Cependant, trier le même inputtableau en utilisant le intégré Array.sort()(dans Chrome / NodeJS):

input.sort((a, b) => a.height - b.height)

Retour:

var unstable = [
  { height: 70, weight: 140 },
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 100 },
  { height: 100, weight: 80 },
  { height: 100, weight: 135 },
  { height: 100, weight: 120 },
  { height: 110, weight: 115 }
]

Ressources

• Wikipédia
• MDN
• JSFiddle

Mettre à jour

Array.prototype.sort est désormais stable dans V8 v7.0 / Chrome 70!

Auparavant, V8 utilisait un QuickSort instable pour les tableaux de plus de 10 éléments. Maintenant, nous utilisons l'algorithme stable TimSort.

la source

Je sais que cette question a reçu une réponse depuis un certain temps, mais il se trouve que j'ai une bonne implémentation de tri de fusion stable pour Array et jQuery dans mon presse-papiers, je vais donc la partager dans l'espoir que certains futurs chercheurs pourraient la trouver utile.

Il vous permet de spécifier votre propre fonction de comparaison comme la normale Array.sort implémentation .

la mise en oeuvre

// Add stable merge sort to Array and jQuery prototypes
// Note: We wrap it in a closure so it doesn't pollute the global
//       namespace, but we don't put it in $(document).ready, since it's
//       not dependent on the DOM
(function() {

  // expose to Array and 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"];

Vous pouvez utiliser le polyfill suivant pour implémenter un tri stable quelle que soit l'implémentation native, en fonction de l'assertion faite dans cette réponse :

// ECMAScript 5 polyfill
Object.defineProperty(Array.prototype, 'stableSort', {
  configurable: true,
  writable: true,
  value: function stableSort (compareFunction) {
    'use strict'

    var length = this.length
    var entries = Array(length)
    var index

    // wrap values with initial indices
    for (index = 0; index < length; index++) {
      entries[index] = [index, this[index]]
    }

    // sort with fallback based on initial indices
    entries.sort(function (a, b) {
      var comparison = Number(this(a[1], b[1]))
      return comparison || a[0] - b[0]
    }.bind(compareFunction))

    // re-map original array to stable sorted values
    for (index = 0; index < length; index++) {
      this[index] = entries[index][1]
    }
    
    return this
  }
})

// usage
const array = Array(500000).fill().map(() => Number(Math.random().toFixed(4)))

const alwaysEqual = () => 0
const isUnmoved = (value, index) => value === array[index]

// not guaranteed to be stable
console.log('sort() stable?', array
  .slice()
  .sort(alwaysEqual)
  .every(isUnmoved)
)
// guaranteed to be stable
console.log('stableSort() stable?', array
  .slice()
  .stableSort(alwaysEqual)
  .every(isUnmoved)
)

// performance using realistic scenario with unsorted big data
function time(arrayCopy, algorithm, compare) {
  var start
  var stop
  
  start = performance.now()
  algorithm.call(arrayCopy, compare)
  stop = performance.now()
  
  return stop - start
}

const ascending = (a, b) => a - b

const msSort = time(array.slice(), Array.prototype.sort, ascending)
const msStableSort = time(array.slice(), Array.prototype.stableSort, ascending)

console.log('sort()', msSort.toFixed(3), 'ms')
console.log('stableSort()', msStableSort.toFixed(3), 'ms')
console.log('sort() / stableSort()', (100 * msSort / msStableSort).toFixed(3) + '%')

L'exécution des tests de performance implémentés ci-dessus stableSort()semble s'exécuter à environ 57% de la vitesse desort() version 59-61 de Chrome.

L'utilisation .bind(compareFunction)de la fonction anonyme enveloppée dans a stableSort()augmenté ces performances relatives d'environ 38% en évitant une référence de portée inutile àcompareFunction chaque appel en l'attribuant au contexte à la place.

Mettre à jour

Opérateur ternaire remplacé par un court-circuit logique, qui a tendance à mieux fonctionner en moyenne (semble faire une différence d'efficacité de 2 à 3%).

Ce qui suit trie le tableau fourni, en appliquant la fonction de comparaison fournie, en retournant la comparaison d'index d'origine lorsque la fonction de comparaison renvoie 0:

function stableSort(arr, compare) {
    var original = arr.slice(0);

    arr.sort(function(a, b){
        var result = compare(a, b);
        return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
    });

    return arr;
}

L'exemple ci-dessous trie un tableau de noms par nom de famille, en conservant l'ordre des noms de famille égaux:

var names = [
	{ surname: "Williams", firstname: "Mary" },
	{ surname: "Doe", firstname: "Mary" }, 
	{ surname: "Johnson", firstname: "Alan" }, 
	{ surname: "Doe", firstname: "John" }, 
	{ surname: "White", firstname: "John" }, 
	{ surname: "Doe", firstname: "Sam" }
]

function stableSort(arr, compare) {
    var original = arr.slice(0);

    arr.sort(function(a, b){
        var result = compare(a, b);
        return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
    });
	
    return arr;
}

stableSort(names, function(a, b) { 
	return a.surname > b.surname ? 1 : a.surname < b.surname ? -1 : 0;
})

names.forEach(function(name) {
	console.log(name.surname + ', ' + name.firstname);
});

Voici une implémentation stable. Cela fonctionne en utilisant le tri natif, mais dans les cas où les éléments se comparent comme égaux, vous rompez 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 approfondi

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 fait allusion à cela, mais n'a pas publié le codez.

mais, ce n'est pas rapide selon ma référence . J'ai modifié un outil de tri de fusion pour accepter une fonction de comparateur personnalisée, et c'était beaucoup plus rapide.

Vous pouvez également utiliser Timsort. C'est un algorithme vraiment compliqué (plus de 400 lignes, donc pas de code source ici), alors voir la description de Wikipedia ou utilisez l'une des implémentations JavaScript existantes:

Implémentation GPL 3 . Présenté sous la forme Array.prototype.timsort. Semble être une réécriture exacte du code Java.

Implémentation du domaine public Conçu comme un tutoriel, l'exemple de code montre uniquement son utilisation avec des entiers.

Timsort est un hybride hautement optimisé de tri par fusion et de tri aléatoire et est l'algorithme de tri par défaut en Python et en Java (1.7+). C'est un algorithme compliqué, car il utilise des algorithmes différents pour de nombreux cas particuliers. Mais en conséquence, il est extrêmement rapide dans une grande variété de circonstances.

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

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];

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;
}

console.log(mergeSort(a));

Je dois trier les tableaux multidimensionnels par une colonne arbitraire, puis par une autre. J'utilise cette fonction pour trier:

function sortMDArrayByColumn(ary, sortColumn){

    //Adds a sequential number to each row of the array
    //This is the part that adds stability to the sort
    for(var x=0; x<ary.length; x++){ary[x].index = x;}

    ary.sort(function(a,b){
        if(a[sortColumn]>b[sortColumn]){return 1;}
        if(a[sortColumn]<b[sortColumn]){return -1;}
        if(a.index>b.index){
            return 1;
        }
        return -1;
    });
}

Notez que ary.sort ne renvoie jamais zéro, c'est là que certaines implémentations de la fonction "sort" prennent des décisions qui pourraient ne pas être correctes.

C'est sacrément rapide aussi.

Voici comment vous pouvez étendre l'objet Array par défaut JS avec une méthode prototype utilisant MERGE SORT . Cette méthode permet de trier sur une clé spécifique (premier paramètre) et un ordre donné ('asc' / 'desc' comme deuxième paramètre)

Array.prototype.mergeSort = function(sortKey, direction){
  var unsortedArray = this;
  if(unsortedArray.length < 2) return unsortedArray;

  var middle = Math.floor(unsortedArray.length/2);
  var leftSubArray = unsortedArray.slice(0,middle).mergeSort(sortKey, direction);
  var rightSubArray = unsortedArray.slice(middle).mergeSort(sortKey, direction);

  var sortedArray = merge(leftSubArray, rightSubArray);
  return sortedArray;

  function merge(left, right) {
    var combined = [];
    while(left.length>0 && right.length>0){
      var leftValue = (sortKey ? left[0][sortKey] : left[0]);
      var rightValue = (sortKey ? right[0][sortKey] : right[0]);
      combined.push((direction === 'desc' ? leftValue > rightValue : leftValue < rightValue) ? left.shift() : right.shift())
    }
    return combined.concat(left.length ? left : right)
  }
}

Vous pouvez tester cela vous-même en déposant l'extrait ci-dessus dans la console de votre navigateur, puis en essayant:

var x = [2,76,23,545,67,-9,12];
x.mergeSort(); //[-9, 2, 12, 23, 67, 76, 545]
x.mergeSort(undefined, 'desc'); //[545, 76, 67, 23, 12, 2, -9]

Ou ordre basé sur un champ spécifique dans un tableau d'objets:

var y = [
  {startTime: 100, value: 'cat'},
  {startTime: 5, value: 'dog'},
  {startTime: 23, value: 'fish'},
  {startTime: 288, value: 'pikachu'}
]
y.mergeSort('startTime');
y.mergeSort('startTime', 'desc');

J'avais donc besoin d'un tri stable pour mon application React + Redux, et la réponse de Vjeux m'a aidé. Cependant, ma solution (générique) semble différente des autres que je vois ici jusqu'à présent, donc je la partage au cas où quelqu'un d'autre aurait un cas d'utilisation correspondant:

• Je veux vraiment juste avoir quelque chose de similaire à l' sort()API, où je peux passer une fonction de comparateur.
• Parfois je peux trier sur place, et parfois mes données sont immuables (car Redux) et j'ai besoin d'une copie triée à la place. J'ai donc besoin d'une fonction de tri stable pour chaque cas d'utilisation.
• ES2015.

Ma solution est de créer un tableau typé de indices, puis d'utiliser une fonction de comparaison pour trier ces indices en fonction du tableau à trier. Ensuite, nous pouvons utiliser le trié indicespour trier le tableau d'origine ou créer une copie triée en un seul passage. Si cela est déroutant, pensez-y de cette façon: où vous passeriez normalement une fonction de comparaison comme:

(a, b) => { 
  /* some way to compare a and b, returning -1, 0, or 1 */ 
};

Vous utilisez maintenant à la place:

(i, j) => { 
  let a = arrayToBeSorted[i], b = arrayToBeSorted[j]; 
  /* some way to compare a and b, returning -1 or 1 */
  return i - j; // fallback when a == b
}

La vitesse est bonne; il s'agit essentiellement de l'algorithme de tri intégré, plus deux passes linéaires à la fin et une couche supplémentaire de surdébit d'indirection du pointeur.

Heureux de recevoir des commentaires sur cette approche. Voici ma mise en œuvre complète de celui-ci:

/**
 * - `array`: array to be sorted
 * - `comparator`: closure that expects indices `i` and `j`, and then
 *   compares `array[i]` to `array[j]` in some way. To force stability,
 *   end with `i - j` as the last "comparison".
 * 
 * Example:
 * ```
 *  let array = [{n: 1, s: "b"}, {n: 1, s: "a"}, {n:0, s: "a"}];
 *  const comparator = (i, j) => {
 *    const ni = array[i].n, nj = array[j].n;
 *    return ni < nj ? -1 :
 *      ni > nj ? 1 :
 *        i - j;
 *  };
 *  stableSortInPlace(array, comparator);
 *  // ==> [{n:0, s: "a"}, {n:1, s: "b"}, {n:1, s: "a"}]
 * ```
 */
function stableSortInPlace(array, comparator) {
  return sortFromIndices(array, findIndices(array, comparator));
}

function stableSortedCopy(array, comparator){
  let indices = findIndices(array, comparator);
  let sortedArray = [];
  for (let i = 0; i < array.length; i++){
    sortedArray.push(array[indices[i]]);
  }
  return sortedArray;
}

function findIndices(array, comparator){
  // Assumes we don't have to worry about sorting more than 
  // 4 billion elements; if you know the upper bounds of your
  // input you could replace it with a smaller typed array
  let indices = new Uint32Array(array.length);
  for (let i = 0; i < indices.length; i++) {
    indices[i] = i;
  }
  // after sorting, `indices[i]` gives the index from where
  // `array[i]` should take the value from, so to sort
  // move the value at at `array[indices[i]]` to `array[i]`
  return indices.sort(comparator);
}

// If I'm not mistaken this is O(2n) - each value is moved
// only once (not counting the vacancy temporaries), and 
// we also walk through the whole array once more to check
// for each cycle.
function sortFromIndices(array, indices) {
  // there might be multiple cycles, so we must
  // walk through the whole array to check.
  for (let k = 0; k < array.length; k++) {
    // advance until we find a value in
    // the "wrong" position
    if (k !== indices[k]) {
      // create vacancy to use "half-swaps" trick,
      // props to Andrei Alexandrescu
      let v0 = array[k];
      let i = k;
      let j = indices[k];
      while (j !== k) {
        // half-swap next value
        array[i] = array[j];
        // array[i] now contains the value it should have,
        // so we update indices[i] to reflect this
        indices[i] = i;
        // go to next index
        i = j;
        j = indices[j];
      }
      // put original array[k] back in
      // and update indices
      array[i] = v0;
      indices[i] = i;
    }
  }
  return array;
}

Je sais que cela a reçu de nombreuses réponses. Je voulais juste publier une implémentation rapide de TS pour tous ceux qui ont atterri ici à la recherche de cela.

export function stableSort<T>( array: T[], compareFn: ( a: T, b: T ) => number ): T[] {
    const indices = array.map( ( x: T, i: number ) => ( { element: x, index: i } ) );

    return indices.sort( ( a, b ) => {
        const order = compareFn( a.element, b.element );
        return order === 0 ? a.index - b.index : order;
    } ).map( x => x.element );
}

La méthode ne s'exécute plus sur place, comme le fait le tri natif. Je tiens également à souligner que ce n’est pas le plus efficace. Il ajoute deux boucles de l'ordre O (n). bien que le tri lui-même soit probablement O (n log (n)), il est donc inférieur à cela.

Certaines des solutions mentionnées sont plus performantes, pensant que cela pourrait être moins de code, utilisant également des Array.prototype.sort .

(Pour une solution Javascript, supprimez simplement tous les types)

Selon le blog de développement v8 , caniuse.com Array.sort est déjà stable, comme l'exige la spécification des navigateurs modernes, vous n'avez donc pas besoin de lancer votre propre solution. La seule exception que je peux voir est Edge, qui devrait bientôt passer au chrome et le supporter également.

Le tri par comptage est plus rapide que le tri par fusion (il s'exécute 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 ()
    // start at lowest possible value of m
    start = 0
    step = 1
    // hash all values
    i = 0
    while ( i < k ) {
        var _m = m[i]
        hash [_m] = _m
        i = i + 1
    }
    i = 0
    j = start
    // find all elements within 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 ()<br/>
var sArray = new Array ()<br/><br/>
uArray = [ 10,1,9,2,8,3,7,4,6,5 ]<br/>
sArray = Math.counting_sort ( uArray ) // returns a sorted array