Ich möchte ein Array von ungefähr 200-300 Objekten sortieren, wobei ich nach einem bestimmten Schlüssel und einer bestimmten Reihenfolge (auf / ab) sortiere. Die Reihenfolge der Ergebnisse muss konsistent und stabil sein.

Was wäre der beste Algorithmus, und könnten Sie ein Beispiel für die Implementierung in Javascript geben?

Vielen Dank!

Es ist möglich, eine stabile Sortierung von einer nicht stabilen Sortierfunktion zu erhalten.

Vor dem Sortieren erhalten Sie die Position aller Elemente. Wenn in Ihrer Sortierbedingung beide Elemente gleich sind, sortieren Sie nach der Position.

Tada! Du hast eine stabile Sorte.

Ich habe in meinem Blog einen Artikel darüber geschrieben, wenn Sie mehr über diese Technik und deren Implementierung erfahren möchten: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html

Da Sie nach etwas Stabilem suchen, sollte die Zusammenführungssortierung ausreichen.

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

Der Code ist auf der oben genannten Website zu finden:

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

BEARBEITEN:

Laut diesem Beitrag sieht es so aus, als ob Array.Sort in einigen Implementierungen eine Zusammenführungssortierung verwendet.

Etwas kürzere Version derselben Sache mit ES2017-Funktionen wie Pfeilfunktionen und Destrukturierung:

Funktion

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)

Es akzeptiert Eingabearrays und Vergleichsfunktionen:

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

Es gibt auch ein neues Array zurück, anstatt eine direkte Sortierung wie die integrierte Funktion Array.sort () vorzunehmen .

Prüfung

Wenn wir das folgende inputArray nehmen, zunächst sortiert nach 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 }
]

Dann sortieren Sie es heightmit stableSort:

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

Ergebnisse in:

// 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 }
]

Sortieren des gleichen inputArrays mithilfe des integrierten Arrays Array.sort()(in Chrome / NodeJS):

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

Kehrt zurück:

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

Ressourcen

• Wikipedia
• MDN
• JSFiddle

Aktualisieren

Array.prototype.sort ist jetzt stabil in V8 v7.0 / Chrome 70!

Bisher verwendete V8 einen instabilen QuickSort für Arrays mit mehr als 10 Elementen. Jetzt verwenden wir den stabilen TimSort-Algorithmus.

Quelle

Ich weiß, dass diese Frage seit einiger Zeit beantwortet wurde, aber ich habe zufällig eine gute stabile Implementierung für die Zusammenführungssortierung für Array und jQuery in meiner Zwischenablage. Daher werde ich sie in der Hoffnung teilen, dass einige zukünftige Suchende sie nützlich finden könnten.

Hier können Sie Ihre eigene Vergleichsfunktion wie gewohnt angeben Array.sort Implementierung .

Implementierung

// 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;
  }
})();

Beispiel Verwendung

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"];

Sie können die folgende Polyfüllung verwenden, um eine stabile Sortierung unabhängig von der nativen Implementierung zu implementieren, basierend auf der in dieser Antwort gemachten Aussage :

// 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) + '%')

Das Ausführen der oben implementierten Leistungstests stableSort()scheint mit etwa 57% der Geschwindigkeit von sort()Chrome Version 59-61 zu laufen .

Durch .bind(compareFunction)die Verwendung der verpackten anonymen Funktion in wurde stableSort()die relative Leistung von etwa 38% gesteigert, indem compareFunctionbei jedem Aufruf ein nicht benötigter Verweis auf den Gültigkeitsbereich vermieden wurde, indem sie stattdessen dem Kontext zugewiesen wurde .

Aktualisieren

Der ternäre Operator wurde in einen logischen Kurzschluss geändert, der im Durchschnitt tendenziell besser abschneidet (scheint einen Wirkungsgradunterschied von 2-3% zu bewirken).

Im Folgenden wird das bereitgestellte Array sortiert, indem die bereitgestellte Vergleichsfunktion angewendet wird und der ursprüngliche Indexvergleich zurückgegeben wird, wenn die Vergleichsfunktion 0 zurückgibt:

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

Im folgenden Beispiel wird ein Array von Namen nach Nachnamen sortiert, wobei die Reihenfolge der gleichen Nachnamen beibehalten wird:

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

Hier ist eine stabile Implementierung. Es funktioniert mit der nativen Sortierung. In Fällen, in denen Elemente als gleich verglichen werden, unterbrechen Sie die Verknüpfungen anhand der ursprünglichen Indexposition.

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

ein nicht gründlicher Test

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

eine andere Antwort darauf an, postete aber nicht den Codez.

Aber es ist nicht schnell nach meinem Benchmark . Ich habe ein Merge-Sort-Impl so geändert , dass es eine benutzerdefinierte Komparatorfunktion akzeptiert, und es war viel schneller.

Sie können auch Timsort verwenden. Dies ist ein wirklich komplizierter Algorithmus (mehr als 400 Zeilen, daher hier kein Quellcode). Sehen Sie sich also die Beschreibung von Wikipedia an oder verwenden Sie eine der vorhandenen JavaScript-Implementierungen:

GPL 3-Implementierung . Verpackt als Array.prototype.timsort. Scheint eine exakte Umschreibung von Java-Code zu sein.

Public Domain Implementierung Beispiel gedacht, zeigt der Beispielcode nur die Verwendung mit Ganzzahlen.

Timsort ist eine hochoptimierte Mischung aus Mergesort und Shuffle-Sortierung und der Standardsortieralgorithmus in Python und Java (1.7+). Es ist ein komplizierter Algorithmus, da er für viele Sonderfälle unterschiedliche Algorithmen verwendet. Infolgedessen ist es unter den unterschiedlichsten Umständen extrem schnell.

Ein einfacher mergeSort von 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));

Ich muss mehrdimensionale Arrays nach einer beliebigen Spalte und dann nach einer anderen sortieren. Ich benutze diese Funktion, um zu sortieren:

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

Beachten Sie, dass ary.sort niemals Null zurückgibt. Hier treffen einige Implementierungen der Funktion "sort" Entscheidungen, die möglicherweise nicht richtig sind.

Das ist auch verdammt schnell.

Hier erfahren Sie, wie Sie das JS-Standardarrayobjekt mit einer Prototypmethode unter Verwendung von MERGE SORT erweitern können . Diese Methode ermöglicht das Sortieren nach einem bestimmten Schlüssel (erster Parameter) und einer bestimmten Reihenfolge ('asc' / 'desc' als zweiter Parameter).

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

Sie können dies selbst testen, indem Sie das obige Snippet in Ihre Browserkonsole ablegen und dann versuchen:

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]

Oder Reihenfolge basierend auf einem bestimmten Feld in einem Array von Objekten:

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');

Ich brauchte also eine stabile Sortierung für meine React + Redux-App, und die Antwort von Vjeux hier hat mir geholfen. Meine (generische) Lösung scheint sich jedoch von den anderen zu unterscheiden, die ich bisher hier sehe. Ich teile sie daher, falls jemand anderes einen passenden Anwendungsfall hat:

• Ich möchte wirklich nur etwas Ähnliches wie die sort()API haben, wo ich eine Komparatorfunktion übergeben kann.
• Manchmal kann ich sortieren, und manchmal sind meine Daten unveränderlich (weil Redux), und ich benötige stattdessen eine sortierte Kopie. Ich brauche also eine stabile Sortierfunktion für jeden Anwendungsfall.
• ES2015.

Meine Lösung besteht darin, ein typisiertes Array von zu erstellen indicesund dann eine Vergleichsfunktion zu verwenden, um diese Indizes basierend auf dem zu sortierenden Array zu sortieren. Dann können wir die sortierten verwenden indicesentweder Art des Original - Array oder eine sortierte Kopie in einem einzigen Durchgang erstellen. Wenn das verwirrend ist, denken Sie so: Wo Sie normalerweise eine Vergleichsfunktion übergeben würden wie:

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

Sie verwenden jetzt stattdessen:

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

Geschwindigkeit ist gut; Es handelt sich im Grunde genommen um den integrierten Sortieralgorithmus, plus zwei lineare Durchgänge am Ende und eine zusätzliche Schicht des Overheads der Zeiger-Indirektion.

Freut mich über Feedback zu diesem Ansatz. Hier ist meine vollständige Implementierung davon:

/**
 * - `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;
}

Ich weiß, dass dies viel beantwortet wurde. Ich wollte nur eine schnelle TS-Implementierung für alle veröffentlichen, die hier gelandet sind und danach suchen.

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

Die Methode wird nicht mehr direkt ausgeführt, wie dies bei der nativen Sortierung der Fall ist. Ich möchte auch darauf hinweisen, dass es nicht das effizienteste ist. Es werden zwei Schleifen der Ordnung O (n) hinzugefügt. Obwohl die Sortierung selbst höchstwahrscheinlich O (n log (n)) ist, ist sie geringer.

Einige der genannten Lösungen sind leistungsfähiger, obwohl dies möglicherweise weniger Code ist, auch wenn interner Code verwendet wird Array.prototype.sort .

(Für eine Javascript-Lösung entfernen Sie einfach alle Typen.)

Nach dem DevBlog v8 und caniuse.com Array.sort ist bereits stabil wie in modernen Browsern von der Spezifikation erforderlich, so dass Sie nicht brauchen Ihre eigene Lösung zu rollen. Die einzige Ausnahme, die ich sehen kann, ist Edge, das bald auf Chrom umsteigen und es ebenfalls unterstützen sollte.

Das Zählen der Sortierung ist schneller als das Zusammenführen der Sortierung (sie wird in O (n) -Zeit ausgeführt) und ist für die Verwendung mit ganzen Zahlen vorgesehen.

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
}

Beispiel:

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