Array.prototype.sort()

compareFn Optional

Eine Funktion, die die Reihenfolge der Elemente bestimmt. Die Funktion wird mit den folgenden Argumenten aufgerufen:

a

Das erste Element zum Vergleich. Wird niemals undefined sein.

b

Das zweite Element zum Vergleich. Wird niemals undefined sein.

Es sollte eine Zahl zurückgeben, wobei:

• Ein negativer Wert anzeigt, dass a vor b kommen sollte.
• Ein positiver Wert anzeigt, dass a nach b kommen sollte.
• Null oder NaN anzeigt, dass a und b als gleich betrachtet werden.

Zum Merken: (a, b) => a - b sortiert Zahlen in aufsteigender Reihenfolge.

Wenn diese weggelassen wird, werden die Array-Elemente in Strings umgewandelt und dann gemäß dem Unicode-Codepunktwert jedes Zeichens sortiert.

Die Referenz auf das ursprüngliche Array, jetzt sortiert. Beachten Sie, dass das Array in-place sortiert wird und keine Kopie erstellt wird.

Wird compareFn nicht angegeben, werden alle nicht undefined-Array-Elemente sortiert, indem sie in Strings umgewandelt und Strings in der Reihenfolge der UTF-16-Codeeinheiten verglichen werden. Zum Beispiel kommt „banana“ vor „cherry“. Bei einer numerischen Sortierung kommt 9 vor 80, aber da Zahlen in Strings umgewandelt werden, kommt "80" im Unicodesystem vor "9". Alle undefined-Elemente werden ans Ende des Arrays sortiert.

Die sort()-Methode bewahrt leere Plätze. Wenn das Ausgangsarray lückenhaft ist, werden die leeren Plätze an das Ende des Arrays verschoben und kommen immer nach allen undefined.

Wenn compareFn angegeben ist, werden alle nicht undefined-Array-Elemente gemäß dem Rückgabewert der Vergleichsfunktion sortiert (alle undefined-Elemente werden ans Ende des Arrays sortiert, ohne einen Aufruf von compareFn).

Daher hat die Vergleichsfunktion folgende Form:

function compareFn(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  } else if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

Formeller ausgedrückt sollte der Vergleich mit den folgenden Eigenschaften ausgestattet sein, um ein korrektes Sortierverhalten sicherzustellen:

• Rein: Der Vergleich verändert nicht die zu vergleichenden Objekte oder einen externen Zustand. (Dies ist wichtig, da es keine Garantie gibt, wann und wie oft der Vergleich aufgerufen wird, daher sollte jeder Aufruf keine sichtbaren Effekte nach außen hin erzeugen.)
• Stabil: Der Vergleich gibt dasselbe Ergebnis mit demselben Paar von Eingaben zurück.
• Reflexiv: compareFn(a, a) === 0.
• Antisymmetrisch: compareFn(a, b) und compareFn(b, a) müssen beide 0 oder entgegengesetzte Vorzeichen haben.
• Transitiv: Wenn compareFn(a, b) und compareFn(b, c) beide positiv, null oder negativ sind, dann hat compareFn(a, c) die gleiche Positivität wie die vorherigen beiden.

Ein Vergleich, der die obigen Einschränkungen erfüllt, kann immer 1, 0 und -1 zurückgeben oder konsistent 0 zurückgeben. Wenn ein Vergleich beispielsweise nur 1 und 0 zurückgibt oder nur 0 und -1, wird er nicht zuverlässig sortieren, da die Antisymmetrie verletzt wird. Ein Vergleich, der immer 0 zurückgibt, führt dazu, dass das Array überhaupt nicht verändert wird, ist jedoch trotzdem zuverlässig.

Der standardmäßige lexikografische Vergleich erfüllt alle oben genannten Einschränkungen.

Um Zahlen anstelle von Strings zu vergleichen, kann die Vergleichsfunktion b von a subtrahieren. Die folgende Funktion sortiert das Array in aufsteigender Reihenfolge (wenn es kein NaN enthält):

function compareNumbers(a, b) {
  return a - b;
}

Die sort()-Methode ist generisch. Sie erwartet nur, dass der this-Wert eine length-Eigenschaft und ganze Zahl-eingefasste Eigenschaften hat. Obwohl Zeichenfolgen auch array-ähnlich sind, ist diese Methode nicht geeignet, auf sie angewendet zu werden, da Zeichenfolgen unveränderlich sind.

Das folgende Beispiel erstellt vier Arrays und zeigt das ursprüngliche Array, dann die sortierten Arrays an. Die numerischen Arrays werden ohne Vergleichsfunktion und dann unter Verwendung einer solchen sortiert.

const stringArray = ["Blue", "Humpback", "Beluga"];
const numberArray = [40, 1, 5, 200];
const numericStringArray = ["80", "9", "700"];
const mixedNumericArray = ["80", "9", "700", 40, 1, 5, 200];

function compareNumbers(a, b) {
  return a - b;
}

stringArray.join(); // 'Blue,Humpback,Beluga'
stringArray.sort(); // ['Beluga', 'Blue', 'Humpback']

numberArray.join(); // '40,1,5,200'
numberArray.sort(); // [1, 200, 40, 5]
numberArray.sort(compareNumbers); // [1, 5, 40, 200]

numericStringArray.join(); // '80,9,700'
numericStringArray.sort(); // ['700', '80', '9']
numericStringArray.sort(compareNumbers); // ['9', '80', '700']

mixedNumericArray.join(); // '80,9,700,40,1,5,200'
mixedNumericArray.sort(); // [1, 200, 40, 5, '700', '80', '9']
mixedNumericArray.sort(compareNumbers); // [1, 5, '9', 40, '80', 200, '700']

Arrays von Objekten können sortiert werden, indem der Wert einer ihrer Eigenschaften verglichen wird.

const items = [
  { name: "Edward", value: 21 },
  { name: "Sharpe", value: 37 },
  { name: "And", value: 45 },
  { name: "The", value: -12 },
  { name: "Magnetic", value: 13 },
  { name: "Zeros", value: 37 },
];

// sort by value
items.sort((a, b) => a.value - b.value);

// sort by name
items.sort((a, b) => {
  const nameA = a.name.toUpperCase(); // ignore upper and lowercase
  const nameB = b.name.toUpperCase(); // ignore upper and lowercase
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }

  // names must be equal
  return 0;
});

Um Zeichenfolgen mit nicht-ASCII-Zeichen zu sortieren, d.h. Zeichenfolgen mit Akzentzeichen (e, é, è, a, ä, etc.), Zeichenfolgen aus anderen als der englischen Sprache, verwenden Sie String.prototype.localeCompare(). Diese Funktion kann diese Zeichen vergleichen, damit sie in der richtigen Reihenfolge erscheinen.

const items = ["réservé", "premier", "communiqué", "café", "adieu", "éclair"];
items.sort((a, b) => a.localeCompare(b));

// items is ['adieu', 'café', 'communiqué', 'éclair', 'premier', 'réservé']

Die compareFn kann mehrfach pro Element im Array aufgerufen werden. Je nach Art von compareFn kann dies zu einem hohen Overhead führen. Je mehr Arbeit ein compareFn verrichtet und je mehr Elemente zu sortieren sind, desto effizienter kann es sein, map() zum Sortieren zu verwenden. Die Idee besteht darin, das Array einmal zu durchlaufen, um die tatsächlich zum Sortieren verwendeten Werte in ein temporäres Array zu extrahieren, das temporäre Array zu sortieren und dann das temporäre Array zu durchlaufen, um die richtige Reihenfolge zu erreichen.

// the array to be sorted
const data = ["delta", "alpha", "charlie", "bravo"];

// temporary array holds objects with position and sort-value
const mapped = data.map((v, i) => {
  return { i, value: someSlowOperation(v) };
});

// sorting the mapped array containing the reduced values
mapped.sort((a, b) => {
  if (a.value > b.value) {
    return 1;
  }
  if (a.value < b.value) {
    return -1;
  }
  return 0;
});

const result = mapped.map((v) => data[v.i]);

Eine Open-Source-Bibliothek namens mapsort steht zur Verfügung, die diesen Ansatz anwendet.

Die sort()-Methode gibt eine Referenz auf das ursprüngliche Array zurück, daher verändert das Verändern des zurückgegebenen Arrays auch das ursprüngliche Array.

const numbers = [3, 1, 4, 1, 5];
const sorted = numbers.sort((a, b) => a - b);
// numbers and sorted are both [1, 1, 3, 4, 5]
sorted[0] = 10;
console.log(numbers[0]); // 10

Falls Sie möchten, dass sort() das ursprüngliche Array nicht verändert, sondern ein flach kopiertes Array wie andere Array-Methoden (z.B. map()) zurückgibt, verwenden Sie die toSorted()-Methode. Alternativ können Sie vor dem Aufruf von sort() eine flache Kopie erstellen, indem Sie die spread syntax oder Array.from() verwenden.

const numbers = [3, 1, 4, 1, 5];
// [...numbers] creates a shallow copy, so sort() does not mutate the original
const sorted = [...numbers].sort((a, b) => a - b);
sorted[0] = 10;
console.log(numbers[0]); // 3

Seit Version 10 (oder ECMAScript 2019) diktiert die Spezifikation, dass Array.prototype.sort stabil ist.

Angenommen, Sie hätten eine Liste von Studenten zusammen mit ihren Noten. Beachten Sie, dass die Liste der Studenten bereits im Voraus nach Namen in alphabetischer Reihenfolge sortiert ist:

const students = [
  { name: "Alex", grade: 15 },
  { name: "Devlin", grade: 15 },
  { name: "Eagle", grade: 13 },
  { name: "Sam", grade: 14 },
];

Nach dem Sortieren dieses Arrays nach grade in aufsteigender Reihenfolge:

students.sort((firstItem, secondItem) => firstItem.grade - secondItem.grade);

Hat die Variable students dann den folgenden Wert:

[
  { name: "Eagle", grade: 13 },
  { name: "Sam", grade: 14 },
  { name: "Alex", grade: 15 }, // original maintained for similar grade (stable sorting)
  { name: "Devlin", grade: 15 }, // original maintained for similar grade (stable sorting)
];

Es ist wichtig zu beachten, dass Studenten, die die gleiche Note haben (zum Beispiel Alex und Devlin), in der gleichen Reihenfolge wie vor dem Sortieren bleiben. Dies ist das, was ein stabiles Sortierverfahren garantiert.

Vor Version 10 (oder ECMAScript 2019) war die Stabilität des Sortierens nicht garantiert, was bedeutete, dass man mit dem folgenden enden konnte:

[
  { name: "Eagle", grade: 13 },
  { name: "Sam", grade: 14 },
  { name: "Devlin", grade: 15 }, // original order not maintained
  { name: "Alex", grade: 15 }, // original order not maintained
];

Wenn eine Vergleichsfunktion nicht alle in der Beschreibung erklärten Anforderungen an Reinheit, Stabilität, Reflexivität, Antisymmetrie und Transitivität erfüllt, ist das Verhalten des Programms nicht vordefiniert.

Beispielsweise betrachten Sie diesen Code:

const arr = [3, 1, 4, 1, 5, 9];
const compareFn = (a, b) => (a > b ? 1 : 0);
arr.sort(compareFn);

Die compareFn-Funktion hier ist nicht richtig geformt, weil sie die Antisymmetrie nicht erfüllt: Wenn a > b, gibt sie 1 zurück; aber durch Austauschen von a und b gibt sie 0 statt eines negativen Wertes zurück. Daher wird das resultierende Array in verschiedenen Engines unterschiedlich sein. Zum Beispiel würden V8 (verwendet von Chrome, Node.js, etc.) und JavaScriptCore (verwendet von Safari) das Array überhaupt nicht sortieren und [3, 1, 4, 1, 5, 9] zurückgeben, während SpiderMonkey (verwendet von Firefox) das Array in aufsteigender Reihenfolge zurückgeben wird, als [1, 1, 3, 4, 5, 9].

Wird die compareFn-Funktion jedoch leicht geändert, sodass sie -1 oder 0 zurückgibt:

const arr = [3, 1, 4, 1, 5, 9];
const compareFn = (a, b) => (a > b ? -1 : 0);
arr.sort(compareFn);

Dann sortieren V8 und JavaScriptCore es in absteigender Reihenfolge, als [9, 5, 4, 3, 1, 1], während SpiderMonkey es unverändert lässt: [3, 1, 4, 1, 5, 9].

Aufgrund dieser Inkonsistenz der Implementierung wird immer empfohlen, Ihr Vergleich richtig zu formen, indem Sie die fünf Einschränkungen befolgen.

Leere Plätze werden an das Ende des Arrays verschoben.

console.log(["a", "c", , "b"].sort()); // ['a', 'b', 'c', empty]
console.log([, undefined, "a", "b"].sort()); // ["a", "b", undefined, empty]

Die sort()-Methode liest die length-Eigenschaft von this. Sie sammelt dann alle existierenden ganzzahligeigenschlüsselten Eigenschaften im Bereich von 0 bis length - 1, sortiert sie und schreibt sie zurück. Wenn im Bereich fehlende Eigenschaften vorhanden sind, werden die entsprechenden nachfolgenden Eigenschaften gelöscht, als ob die nicht existenten Eigenschaften zum Ende hin sortiert werden.

const arrayLike = {
  length: 3,
  unrelated: "foo",
  0: 5,
  2: 4,
};
console.log(Array.prototype.sort.call(arrayLike));
// { '0': 4, '1': 5, length: 3, unrelated: 'foo' }

• Polyfill von Array.prototype.sort mit modernem Verhalten wie stabilem Sortieren in core-js
• Leitfaden für indexierte Sammlungen
• Array
• Array.prototype.reverse()
• Array.prototype.toSorted()
• String.prototype.localeCompare()
• TypedArray.prototype.sort()
• Dinge in V8 sortieren auf v8.dev (2018)
• Stabiles Array.prototype.sort auf v8.dev (2019)
• Array.prototype.sort-Stabilität von Mathias Bynens