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 für den Vergleich. Wird niemals undefined sein.

b

Das zweite Element für den Vergleich. Wird niemals undefined sein.

Sie sollte eine Zahl zurückgeben, bei der:

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

Um dies zu merken, denken Sie daran, dass (a, b) => a - b Zahlen in aufsteigender Reihenfolge sortiert.

Wenn weggelassen, 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.

Wenn compareFn nicht angegeben ist, werden alle nicht undefined Array-Elemente sortiert, indem sie in Strings umgewandelt und in der Reihenfolge der UTF-16-Codeunits verglichen werden. Zum Beispiel kommt "banana" vor "cherry". In einer numerischen Sortierung kommt 9 vor 80, aber weil Zahlen in Strings umgewandelt werden, kommt "80" vor "9" in der Unicode-Reihenfolge. Alle undefined Elemente werden ans Ende des Arrays sortiert.

Die sort() Methode bewahrt leere Slots. Wenn das Quellarray spärlich ist, werden die leeren Slots ans Ende des Arrays verschoben und kommen immer nach allen undefined.

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

Die Vergleichsfunktion hat also die 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;
}

Formal wird erwartet, dass der Komparator die folgenden Eigenschaften hat, um ein korrektes Sortierverhalten sicherzustellen:

• Pure: Der Komparator verändert nicht die Objekte, die verglichen werden, oder irgendeinen externen Zustand. (Dies ist wichtig, da es keine Garantie gibt, wann und wie der Komparator aufgerufen wird, sodass jeder Aufruf keine sichtbaren Auswirkungen auf das Äußere haben sollte.)
• Stabil: Der Komparator gibt das gleiche Ergebnis mit dem gleichen Paar von Eingaben zurück.
• Reflexiv: compareFn(a, a) === 0.
• Antisymmetrisch: compareFn(a, b) und compareFn(b, a) müssen entweder beide 0 sein oder entgegengesetzte Vorzeichen haben.
• Transitiv: Wenn compareFn(a, b) und compareFn(b, c) beide positiv, null oder negativ sind, hat compareFn(a, c) die gleiche Vorzeichen wie die beiden vorherigen.

Ein Komparator, der den oben genannten Bedingungen entspricht, kann immer 1, 0 und -1 zurückgeben oder konsistent 0 zurückgeben. Beispielsweise kann ein Komparator, der nur 1 und 0 oder nur 0 und -1 zurückgibt, nicht zuverlässig sortieren, da die Antisymmetrie verletzt wird. Ein Komparator, der immer 0 zurückgibt, bewirkt, dass das Array überhaupt nicht verändert wird, ist aber dennoch zuverlässig.

Der standardmäßige lexikografische Komparator erfüllt alle obigen Bedingungen.

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 integer-indizierte Eigenschaften hat. Obwohl Strings auch array-ähnlich sind, ist diese Methode nicht geeignet, auf sie angewendet zu werden, da Strings unveränderbar sind.

Das folgende Beispiel erstellt vier Arrays und zeigt das ursprüngliche Array an, gefolgt von den sortierten Arrays. Die numerischen Arrays werden ohne Vergleichsfunktion sortiert und dann mithilfe einer 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 Strings mit nicht-ASCII-Zeichen zu sortieren, also Strings mit Akzentzeichen (e, é, è, a, ä, usw.), Strings aus anderen Sprachen als Englisch, verwenden Sie String.prototype.localeCompare(). Diese Funktion kann diese Zeichen so vergleichen, dass sie in die richtige 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 für jedes Element innerhalb des Arrays mehrmals aufgerufen werden. Abhängig von der Natur der compareFn kann dies zu einem hohen Overhead führen. Je mehr Arbeit eine compareFn leistet und je mehr Elemente es zu sortieren gibt, desto effizienter kann es sein, map() für das Sortieren zu verwenden. Die Idee ist, einmal durch das Array zu traversieren, um die tatsächlichen Werte zu extrahieren, die zum Sortieren verwendet werden, in ein temporäres Array, das temporäre Array zu sortieren und dann das temporäre Array zu traversieren, 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]);

Es gibt eine Open-Source-Bibliothek namens mapsort, die diesen Ansatz anwendet.

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

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 zurückgibt wie andere Array-Methoden (z.B. map()), verwenden Sie die toSorted() Methode. Alternativ können Sie eine flache Kopie vor dem Aufruf von sort() 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) schreibt die Spezifikation vor, dass Array.prototype.sort stabil ist.

Zum Beispiel, sagen wir, Sie hätten eine Liste von Schülern zusammen mit ihren Noten. Beachten Sie, dass die Liste der Schüler bereits vorab nach Namen alphabetisch 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 students Variable 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, darauf hinzuweisen, dass Schüler, die die gleiche Note haben (zum Beispiel Alex und Devlin), in der gleichen Reihenfolge bleiben wie vor dem Aufruf der Sortierung. Dies ist das, was ein stabiler Sortieralgorithmus garantiert.

Vor Version 10 (oder ECMAScript 2019) war die Stabilität der Sortierung nicht garantiert, was bedeutet, dass Sie mit dem folgenden Ergebnis enden könnten:

[
  { 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 Regeln der Reinheit, Stabilität, Reflexivität, Antisymmetrie und Transitivität, wie in der Beschreibung erläutert, erfüllt, ist das Verhalten des Programms nicht wohldefiniert.

Betrachten Sie zum Beispiel diesen Code:

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

Die compareFn Funktion ist hier nicht gut geformt, weil sie nicht die Antisymmetrie erfüllt: Wenn a > b, gibt sie 1 zurück; aber durch Vertauschen von a und b gibt sie 0 zurück anstelle eines negativen Wertes. 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 aufsteigend sortiert zurückgeben würde, als [1, 1, 3, 4, 5, 9].

Wenn jedoch die compareFn Funktion leicht geändert wird, 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 sortiert V8 und JavaScriptCore es absteigend, als [9, 5, 4, 3, 1, 1], während SpiderMonkey es unverändert zurückgibt: [3, 1, 4, 1, 5, 9].

Aufgrund dieser Implementierungsinkonsistenz wird dringend empfohlen, dass Ihr Komparator gut geformt ist, indem er den fünf Bedingungen folgt.

Leere Slots werden ans 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 integer-indizierten Eigenschaften im Bereich von 0 bis length - 1, sortiert sie und schreibt sie zurück. Wenn es fehlende Eigenschaften im Bereich gibt, werden die entsprechenden folgenden Eigenschaften wie gelöscht, als ob die nicht existierenden Eigenschaften ans Ende 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 stabile Sortierung in core-js
• Leitfaden für indizierte Sammlungen
• Array
• Array.prototype.reverse()
• Array.prototype.toSorted()
• String.prototype.localeCompare()
• TypedArray.prototype.sort()
• Getting things sorted in V8 auf v8.dev (2018)
• Stabile Array.prototype.sort auf v8.dev (2019)
• Array.prototype.sort Stabilität von Mathias Bynens