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 sollte.
• Ein positiver Wert anzeigt, dass a nach b kommen sollte.
• Null oder NaN anzeigt, dass a und b als gleich angesehen werden.

Um sich 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, nun sortiert. Beachten Sie, dass das Array in place sortiert wird, und keine Kopie erstellt wird.

Wenn compareFn nicht bereitgestellt wird, werden alle nicht-undefined Array-Elemente sortiert, indem sie in Strings umgewandelt und die daraus resultierenden Strings in der Reihenfolge der UTF-16-Codeeinheiten verglichen werden. Zum Beispiel kommt "banana" vor "cherry". In einer numerischen Sortierung kommt 9 vor 80, aber da Zahlen in Strings umgewandelt werden, kommt "80" in der Unicode-Reihenfolge vor "9". Alle undefined Elemente werden am Ende des Arrays sortiert.

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

Wenn compareFn bereitgestellt wird, werden alle nicht-undefined Array-Elemente gemäß dem Rückgabewert der Vergleichsfunktion sortiert (alle undefined Elemente werden an das Ende des Arrays sortiert, ohne Aufruf von compareFn).

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

Formeller ausgedrückt, der Komparator sollte die folgenden Eigenschaften haben, um ein korrektes Sortierverhalten zu gewährleisten:

• Pure: Der Komparator verändert nicht die Objekte, die verglichen werden, oder einen externen Zustand. (Dies ist wichtig, da nicht garantiert ist, wann und wie der Komparator aufgerufen wird, daher sollte kein bestimmter Aufruf sichtbare Effekte nach außen erzeugen.)
• Stabil: Der Komparator liefert dasselbe Ergebnis mit demselben Paar von Eingaben.
• 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, hat compareFn(a, c) dieselbe Positivität wie die vorherigen beiden.

Ein Komparator, der den obigen Beschränkungen entspricht, wird immer in der Lage sein, alle von 1, 0 und -1 zurückzugeben oder konsistent 0 zurückzugeben. Wenn ein Komparator beispielsweise nur 1 und 0 zurückgibt oder nur 0 und -1 zurückgibt, kann er nicht zuverlässig sortieren, da die Antisymmetrie gebrochen ist. Ein Komparator, der immer 0 zurückgibt, wird das Array überhaupt nicht verändern, ist aber dennoch zuverlässig.

Der Standard-leixkografische Komparator erfüllt alle obigen Beschrä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 integer-indizierte Eigenschaften hat. Obwohl Strings ebenfalls Array-ähnlich sind, ist diese Methode nicht geeignet, um auf ihnen angewendet zu werden, da Strings unveränderlich sind.

Das folgende Beispiel erstellt vier Arrays und zeigt die Original-Arrays, dann die sortierten Arrays an. Die numerischen Arrays werden ohne Vergleichsfunktion sortiert und dann 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;
});

Zum Sortieren von Strings mit nicht-ASCII Zeichen, d.h. Strings mit Akzentzeichen (z.B. e, é, è, a, ä usw.), Strings aus anderen Sprachen als Englisch, verwenden Sie String.prototype.localeCompare(). Diese Funktion kann diese Zeichen so vergleichen, dass 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 pro Element im Array mehrfach aufgerufen werden. Abhängig von der Natur der compareFn kann dies zu einem hohen Overhead führen. Je mehr Arbeit ein compareFn verrichtet und je mehr Elemente es zu sortieren gibt, desto effizienter kann es sein, map() zum Sortieren zu verwenden. Die Idee ist, das Array einmal zu durchlaufen, um die tatsächlichen Werte, die für die Sortierung verwendet werden, 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) => ({ 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, daher wird durch das Verändern des zurückgegebenen Arrays auch das ursprüngliche Array 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 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) gibt die Spezifikation vor, dass Array.prototype.sort stabil ist.

Beispielsweise nehmen Sie an, Sie hätten eine Liste von Schülern zusammen mit ihren Noten. Beachten Sie, dass die Liste der Schüler bereits nach Name 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);

Wird die Variable students dann 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, die die gleiche Note haben (z.B. Alex und Devlin), in derselben Reihenfolge bleiben wie vor dem Aufrufen der Sortierung. Dies ist, was ein stabiler Sortieralgorithmus garantiert.

Vor Version 10 (oder ECMAScript 2019) war die Sortierstabilität nicht garantiert, was bedeutete, dass Sie mit dem Folgenden enden konnten:

[
  { 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 für Reinheit, Stabilität, Reflexivität, Antisymmetrie und Transitivität, wie in der Beschreibung erklärt, 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 hier ist nicht wohldefiniert, weil sie die Antisymmetrie nicht erfüllt: wenn a > b, gibt sie 1 zurück; aber durch Vertauschen von a und b gibt sie 0 anstelle eines negativen Werts zurück. Daher wird das resultierende Array zwischen den 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].

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 inkonsistenten Implementierung wird stets empfohlen, Ihren Komparator wohldefiniert zu machen, 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 Methode sort() liest die length-Eigenschaft von this. Dann sammelt sie alle vorhandenen integer-indizierten Eigenschaften im Bereich von 0 bis length - 1, sortiert sie und schreibt sie zurück. Wenn in diesem Bereich Eigenschaften fehlen, werden die entsprechenden nachfolgenden Eigenschaften gelöscht, als ob die nicht vorhandenen Eigenschaften ans Ende sortiert würden.

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()
• Sortieren in V8 auf v8.dev (2018)
• Stabile Array.prototype.sort auf v8.dev (2019)
• Array.prototype.sort Stabilität von Mathias Bynens