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.

Sie sollte eine Zahl zurückgeben, wobei:

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

Um sich dies zu merken: (a, b) => a - b sortiert Zahlen in aufsteigender Reihenfolge.

Wenn nicht angegeben, werden die Array-Elemente in Strings konvertiert und dann gemäß dem Unicode-Codepunktwert jedes Zeichens sortiert.

Die Referenz auf das ursprüngliche, nun sortierte Array. 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 durch Konvertieren in Strings und Vergleichen der Strings in UTF-16-Codeeinheitenreihenfolge sortiert. Zum Beispiel kommt "banana" vor "cherry". Bei einer numerischen Sortierung kommt 9 vor 80, aber da Zahlen in Strings konvertiert werden, kommt "80" im Unicode vor "9". Alle undefined-Elemente werden an das Ende des Arrays sortiert.

Die sort()-Methode bewahrt leere Slots. Wenn das Quell-Array sparse ist, werden die leeren Slots 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 dass compareFn aufgerufen wird).

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

Formell sollte der Vergleich folgende Eigenschaften haben, um das korrekte Sortierverhalten zu gewährleisten:

• Pure: Der Vergleich verändert nicht die zu vergleichenden Objekte oder einen anderen äußeren Zustand. (Dies ist wichtig, weil es keine Garantie gibt, wann und wie der Vergleich aufgerufen wird, daher sollte ein bestimmter Aufruf keine sichtbaren Effekte nach außen haben.)
• Stabil: Der Vergleich gibt für dasselbe Paar von Eingaben dasselbe Ergebnis zurück.
• Reflexiv: compareFn(a, a) === 0.
• Anti-symmetrisch: 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, hat compareFn(a, c) dieselbe Positivität wie die vorherigen zwei.

Ein Vergleich, der die oben genannten Einschränkungen erfüllt, kann immer 1, 0 und -1 zurückgeben, oder konsistent 0 zurückgeben. Ein Vergleich, der immer 0 zurückgibt, führt dazu, dass das Array nicht verändert wird, ist aber dennoch zuverlässig.

Der Standard-Lexikografische-Vergleich entspricht allen 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 (sofern 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, eignet sich diese Methode nicht dafür, auf ihnen angewendet zu werden, da Strings 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 sortiert und danach mit einer.

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, das heißt Strings mit Akzentbuchstaben (e, é, è, a, ä usw.), Strings aus anderen Sprachen als Englisch, verwenden Sie String.prototype.localeCompare(). Diese Funktion kann diese Zeichen vergleichen, sodass 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 innerhalb des Arrays mehrmals pro Element aufgerufen werden. Abhängig von der Art der compareFn kann dies einen hohen Overhead verursachen. 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, das Array einmal zu durchlaufen, um die tatsächlichen Werte in ein temporäres Array zu extrahieren, das für das Sortieren verwendet wird, 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) => ({ 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 verfolgt.

Die sort()-Methode gibt eine Referenz auf das ursprüngliche Array zurück, sodass die Änderung des zurückgegebenen Arrays auch das ursprüngliche Array ä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 modifiziert, sondern ein flach-kopiertes Array zurückgibt, wie es andere Array-Methoden tun (z.B. map()), verwenden Sie die toSorted()-Methode. Alternativ können Sie eine flache Kopie erstellen, bevor Sie sort() aufrufen, 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) gibt die Spezifikation vor, dass Array.prototype.sort stabil ist.

Zum Beispiel, nehmen Sie an, Sie hätten eine Liste von Schülern zusammen mit ihren Noten. Beachten Sie, dass die Schülerliste bereits nach Namen in alphabetischer Reihenfolge vorsortiert 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);

Der students-Variable wird dann den folgenden Wert haben:

[
  { 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 Schüler mit derselben Note (zum Beispiel Alex und Devlin) in derselben Reihenfolge wie vor dem Aufruf der Sortierung bleiben. Dies ist, was ein stabiler Sortieralgorithmus garantiert.

Vor Version 10 (oder ECMAScript 2019) war die Stabilität der Sortierung nicht garantiert, was bedeutete, dass Sie möglicherweise das folgende Ergebnis erhalten 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 von Reinheit, Stabilität, Reflexivität, Anti-Symmetrie und Transitivität, wie in der Beschreibung erklärt, einhält, 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 hier ist nicht gut geformt, da sie nicht die Anti-Symmetrie erfüllt: Wenn a > b, gibt sie 1 zurück; aber wenn a und b vertauscht werden, gibt sie 0 anstelle eines negativen Werts zurück. Daher wird das resultierende Array je nach Engine 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 wird, als [1, 1, 3, 4, 5, 9].

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

Aufgrund dieser Implementierungskonsistenz wird immer empfohlen, Ihren Vergleich so zu gestalten, dass er den fünf Einschränkungen entspricht.

Leere Slots 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 vorhandenen integer-indizierten Eigenschaften im Bereich von 0 bis length - 1, sortiert sie und schreibt sie zurück. Wenn es fehlende Eigenschaften in dem Bereich gibt, werden die entsprechenden angehängten Eigenschaften gelöscht, als ob die nicht existierenden Eigenschaften zum Ende sortiert wurden.

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 zu indizierten Sammlungen
• Array
• Array.prototype.reverse()
• Array.prototype.toSorted()
• String.prototype.localeCompare()
• TypedArray.prototype.sort()
• Konzepte der Sortierung in V8 auf v8.dev (2018)
• Stabile Array.prototype.sort auf v8.dev (2019)
• Array.prototype.sort-Stabilität von Mathias Bynens