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 betrachtet werden.

Merken Sie sich, dass (a, b) => a - b Zahlen in aufsteigender Reihenfolge sortiert.

Wenn diese Funktion weggelassen wird, werden die Array-Elemente in Strings umgewandelt und dann entsprechend dem Unicode-Kodepunkt-Wert jedes Zeichens sortiert.

Die Referenz auf das ursprüngliche Array, das nun sortiert ist. Beachten Sie, dass das Array in place sortiert wird und keine Kopie angefertigt wird.

Wenn compareFn nicht bereitgestellt wird, werden alle nicht undefined-Elemente des Arrays sortiert, indem sie in Strings umgewandelt werden und 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" vor "9" in der Unicode-Reihenfolge. Alle undefined-Elemente werden an das Ende des Arrays sortiert.

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

Wenn compareFn bereitgestellt wird, werden alle nicht undefined-Elemente gemäß 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;
}

Formeller erwartet man, dass der Komparator die folgenden Eigenschaften hat, um ein korrektes Sortierverhalten sicherzustellen:

• Rein: Der Komparator verändert nicht die Objekte, die verglichen werden oder irgendeinen externen Zustand.
• Stabil: Der Komparator gibt mit demselben Paar von Eingaben dasselbe Ergebnis 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, dann hat compareFn(a, c) dieselbe Positivität wie die vorherigen beiden.

Ein Komparator, der die obigen Beschränkungen einhält, kann immer alle von 1, 0 und -1 zurückgeben oder konsistent 0 zurückgeben. Beispielsweise, wenn ein Komparator nur 1 und 0 oder nur 0 und -1 zurückgibt, kann er möglicherweise nicht zuverlässig sortieren, weil die Antisymmetrie gebrochen wird. Ein Komparator, der immer 0 zurückgibt, wird das Array überhaupt nicht verändern, ist aber trotzdem zuverlässig.

Der Standard-Lexikographische Komparator erfüllt alle obigen 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 (falls 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 Zeichenfolgen ebenfalls array-ähnlich sind, ist diese Methode nicht geeignet, um 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 eine 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 mit 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 (e, é, è, a, ä, etc.) oder Zeichen aus anderen Sprachen, 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 für jedes Element im Array mehrmals aufgerufen werden. Abhängig von der Art der compareFn kann dies einen hohen Overhead verursachen. Je mehr Arbeit eine compareFn erledigt und je mehr Elemente zu sortieren sind, desto effizienter kann es sein, map() zum Sortieren zu verwenden. Die Idee ist, das Array einmal zu durchlaufen, um die tatsächlich für die Sortierung 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 korrekte 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 umsetzt.

Die sort() Methode gibt eine Referenz auf das ursprüngliche Array zurück. Beim Verändern des zurückgegebenen Arrays wird daher auch das ursprüngliche Array geä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 es andere Array-Methoden (z.B. map()) tun, 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.

Beispielsweise, nehmen wir an, Sie haben eine Liste von Studenten zusammen mit deren Noten. Beachten Sie, dass die Liste der Studenten 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);

Wird die Variable students 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 Studenten, die dieselbe Note haben (zum Beispiel Alex und Devlin), in derselben Reihenfolge bleiben wie vor dem Aufruf der Sortierung. Dies ist, was ein stabiles Sortieralgorithmus garantiert.

Vor Version 10 (oder ECMAScript 2019) war die Sortierstabilität nicht garantiert, was bedeutet, dass Sie mit dem Folgenden 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 der Reine-, Stabil-, Reflexiv-, Antisymmetrie- und Transitivitätsregeln erfüllt, wie im Abschnitt Beschreibung erklärt, ist das Programmverhalten nicht wohldefiniert.

Betrachten Sie beispielsweise diesen Code:

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

Die compareFn hier ist nicht wohldefiniert, denn sie erfüllt nicht die Antisymmetrie: wenn a > b, gibt sie 1 zurück; aber indem a und b umgedreht werden, gibt sie 0 anstelle eines negativen Werts zurück. Daher wird das resultierende Array in verschiedenen Engines unterschiedlich sein. Zum Beispiel würde 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 sortieren 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 als-is zurückgibt: [3, 1, 4, 1, 5, 9].

Aufgrund dieser Implementierungskonsistenz wird immer geraten, seinen Comparator wohldefiniert zu machen, indem man die fünf Einschränkungen befolgt.

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 des this. Sie sammelt dann alle existierenden integer-indizierten Eigenschaften im Bereich von 0 bis length - 1, sortiert sie und schreibt sie zurück. Wenn im Bereich Eigenschaften fehlen, werden die entsprechenden End-Eigenschaften gelöscht, als ob die nicht existierenden Eigenschaften ans Ende sortiert wären.

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
• Indizierte Sammlungen Leitfaden
• 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