JavaScript/Objekte/Array/sort

Aus SELFHTML-Wiki
Wechseln zu: Navigation, Suche

Die Methode Array.sort ordnet die Elemente eines Arrays um.

Syntax

array.sort([Vergleichsfunktion])

  • Vergleichsfunktion: optional – eine Callbackfunktion, die entscheidet, in welcher Relation (kleiner, gleich oder größer) zwei Array-Elemente zueinander stehen.

Rückgabewert ist das gerade sortierte Array.

Beschreibung

Wenn keine Vergleichsfunktion übergeben wird, dann werden die Array-Elemente für den Vergleich in Zeichenketten konvertiert und diese unter Verwendung der Operatoren < und > für Zeichenketten verglichen (d. h. an Hand der Unicode-Codepointwerte der verglichenen Zeichen). Die Konvertierung in Zeichenketten geschieht nur für den Vergleich, der Arrayinhalt wird dadurch nicht verändert.

Beispiel

Sortieren von Namen und Zahlen 

var namen  = ['Ina', 'Bettina', 'Tina', 'Martina']; 
var zahlen = [27, 2, 10, 4]; 

namen.sort(); 
zahlen.sort();

console.log(namen);  // [ 'Bettina', 'Ina', 'Martina', 'Tina' ]
console.log(zahlen); // [ 10, 2, 27, 4 ]
Das Beispiel zeigt die Sortierung von Zeichenketten und numerischen Werten.
Beachten Sie, dass die Zahlen des zweiten Arrays ebenfalls alphabetisch und nicht numerisch sortiert worden sind. So steht die 27 wegen der 2 als Anfangszeichen vor der 4!
Zum numerischen Sortieren von Zahlen benötigen Sie eine integrierte Vergleichsfunktion.
Beachten Sie:
  • Die Zahlen des zweiten Arrays wurden ebenfalls alphabetisch und nicht numerisch sortiert. So steht die 27 wegen der 2 als Anfangszeichen vor der 4!
  • Die Sortierung erfolgt aufsteigend. Wenn Sie absteigend sortieren möchten, benötigen Sie eine eigene Vergleichsfunktion, oder Sie rufen nach toSorted() noch die Methode reverse() auf .

Nicht immer möchte man die Arrays mit den unsortierten Daten überschreiben und benötigt statt dessen eine sortierte Kopie. Dafür könnte man das Array zunächst kopieren und dann die Kopie sortieren, es gibt aber seit der Sprachversion ECMAScript 2023 eine Arraymethode, die beides tut: toSorted().

Beispiel

Sortieren mit toSorted

Verwenden der Vergleichsfunktion

Sortieralgorithmen basieren darauf, jeweils zwei Elemente der zu sortierenden Menge miteinander zu vergleichen und je nach Ergebnis die Anordung der Menge zu verändern. Diesen Vergleich kann eine Funktion übernehmen, die von Ihnen zur Verfügung gestellt wird. Dafür muss Ihre Funktion zwei Parameter entgegennehmen, sie miteinander vergleichen und zurückgeben, welche Reihenfolge diese beiden Werte im Sortierergebnis haben sollen.

Erkannte Situation    Rückgabewert
Parameter 1 soll vor Parameter 2 angeordnet werden ein Wert, der kleiner als 0 ist
Parameter 1 soll hinter Parameter 2 angeordnet werden ein Wert, der größer als 0 ist
Parameter 1 und Parameter 2 sind gleichrangig 0

Eine Sortierung nach Zahlenwert lässt sich ganz einfach realisieren, indem man die Differenz der beiden Zahlen bildet:

Sortierung nach Zahlenwert 
const zahlen = [27, 2, 10, 4]; 

zahlen.sort( (a,b) => a-b );
console.log(zahlen);   // [ 2, 4, 10, 27 ]

Die Vergleichsfunktion wurde hier als Pfeilfunktion notiert. Wenn Sie diese Schreibweise nicht kennen, können Sie auch eine anonyme Funktion hinschreiben: 

zahlen.sort( function(a,b) { return a - b; } );

Weshalb funktioniert es hier, einfach nur die Differenz zu bilden? Die Vergleichsfunktion muss drei Fälle unterscheiden: a < b, a = b und a > b. Wenn der Wert in a kleiner ist als der in b, dann wird a - b eine negative Zahl ergeben. Und wenn a größer ist als b, ergibt sich eine positive Zahl. Sind a und b gleich, ist die Differenz 0. Damit ergeben sich genau die Ergebnisse, die toSorted() braucht, um korrekt zu sortieren.

Falls Sie die Zahlen absteigend sortieren wollen, müssen Sie lediglich die Subtraktion umdrehen, also b - a statt a - b rechnen.

Anforderungen an Vergleichsfunktionen

Eine zum Sortieren geeignete Vergleichsfunktion vergleichFkt(a,b) muss ein paar Grundbedingungen erfüllen, damit die Sortierung funktioniert. Letztlich handelt es sich hier um Grundanforderungen an alle Vergleichsoperatoren.

Pur
Die Funktion darf keine Seiteneffekte haben, d. h. sie darf keine Daten außerhalb der Funktion und schon gar nicht die zu vergleichenden Objekte verändern
Stabil
Gleiche Eingaben müssen zu gleichen Ausgaben führen. Manche Sortieralgorithmen vergleichen das gleiche Wertepaar mehrfach miteinander (das ist zumeist einfacher, als sich das Ergebnis bereits gemachter Vergleiche zu merken). Wenn für das gleiche Wertepaar nicht immer das gleiche Ergebnisse entsteht, würde die Sortierung zu einer Zufallsabfolge.
Reflexiv
Die Bedingung vergleichFkt(a, a) == 0 muss für alle Eingabewerte erfüllt werden.
Antisymmetrisch
Die Bedingung vergleichFkt(a, b) == -vergleichFkt(b, a) muss für alle Eingabewerte erfüllt werden (d.h. das Vertauschen der Eingabewerte muss zum entgegengesetzten Vorzeichen des Ergebnisses führen, oder das Ergebnis muss 0 sein).
Transitiv
bezüglich Gleichheit
Wenn die Vergleiche von a mit b und von b mit c beide 0 ergeben, muss auch der Vergleich von a mit c 0 ergeben.
bezüglich Reihenfolge
Wenn die Vergleiche von a mit b und von b mit c beide einen Wert ungleich 0 ergeben und beide Ergebnisse das gleiche Vorzeichen haben, dann muss auch der Vergleich von a mit c ungleich 0 sein und dieses Vorzeichen haben (beispielsweise ist 2 kleiner als 3 und 3 kleiner als 4, deshalb muss auch gelten, dass 2 kleiner als 4 ist).

Stabilität der Sortierung

Ein Sortierverfahren wird stabil genannt, wenn es Elemente, die als gleich erkannt wurden, nicht in ihrer Reihenfolge verändert. Sortiert man nur Zahlen oder Zeichenketten, fällt das nicht weiter auf, bei dem im folgenden Anwendungsbeispiel gezeigten Sortieren von Objekten aber schon.

Sie haben auf die Stabilität des von JavaScript eingesetzten Sortierverfahrens keinen Einfluss. Seit ECMAScript 2019 ist es aber so, dass an JavaScript-Implementierungen die Anforderung gestellt wird, dass das verwendete Verfahren stabil sein muss.

Anwendungsbeispiel: Mehrstufiges Sortieren

Betrachten wir nun ein etwas komplexeres Beispiel. Unser Array, das sortiert werden soll, enthält nun Objekte, die Name, Vorname und weitere Daten zu Personen enthalten. Diese Objekte sollen nach Name sortiert werden, innerhalb gleicher Namen soll nach Vorname sortiert werden. Der Vergleich zweier Objekte muss daher in zwei Stufen erfolgen, deshalb spricht man von mehrstufigem Sortieren.

Ein Array von Personen 
const gamers = [
   { name: 'LAnnister', vorname: 'Tyrion', alter: 30 },    // LAnnister ist Absicht!
   { name: 'Lannister', vorname: 'Jamie', alter: 40 },
   { name: 'Stark', vorname: 'Robb', alter: 16 },
   { name: 'Arryn', vorname: 'Richard', alter: 7 }
];

Eine Möglichkeit, die auf Grund der vom Browser geforderten Stabilität des Sortieralgorithmus funktionieren würde, besteht darin, das Array zunächst nach Vorname zu sortieren und danach nach Name. Das ist aber nicht effizient, vor allem bei längeren Arrays nicht. Sortieralgorithmen haben die fatale Eigenschaft, bei doppelter Menge der Eingabedaten die bis zu vierfache Zeit zu benötigen.

Statt dessen können wir die Mehrstufigkeit auch in der Vergleichsfunktion realisieren.

Mehrstufige Vergleichsfunktion 
const english = new Intl.Collator("en-GB", { usage: "sort" });
function sortPerson(person1, person2) {
   let ergebnis = english.compare(person1.name, person2.name);
   if (ergebnis == 0)
      ergebnis = english.compare(person1.vorname, person2.vorname);
   return ergebnis;
}

gamers.sort(sortPerson);

Das Ergebnis wäre dieses:

  • Arryn, Richard
  • Lannister, Jamie
  • LAnnister, Tyrion
  • Stark, Robb

Das mag überraschen. Der Vergleich "Lannister, Jamie" < "LAnnister, Tyrion" ergibt eigentich false. Aber wir haben in der Sortierfunktion einen Collator verwendet. Dabei handelt es sich um ein Helferobjekt, das Zeichenkettenvergleiche nach den Regeln einer bestimmten Sprache durchführen kann, und dabei zwei Zeichenketten zunächst basierend auf ihren Basiszeichen sortiert (also ohne Rücksicht auf Schreibung oder Akzente). Weitere Informationen dazu finden Sie bei der Beschreibung des Collator-Objekts.

Das Collator-Objekt, das in der Variablen english gespeichert wird, besitzt eine Methode compare(), die zwei Zeichenketten vergleicht und auf Grund der gesetzten Bedingungen eine negative Zahl zurückgibt, wenn die erste Zeichenkette kleiner ist als die zweite, eine positive Zahl, wenn die erste Zeichenkette größer ist und 0, wenn sie als gleich gelten. Wir erhalten also genau das, was toSorted() von uns erwartet.

Die Zweistufigkeit wird dadurch erreicht, dass zunächst die Nachnamen verglichen werden. Ist das Ergebnis dieses Vergleichs 0, wird das Vergleichsergebnis der Vornamen herangezogen.

Die Schwestermethode toSorted kann genauso gut eine Vergleichsfunktion erhalten: 

 const sortedGamers = gamers.toSorted(englishPerson);

Weblinks

Abgerufen von „http://wiki.selfhtml.org/index.php?title=JavaScript/Objekte/Array/sort&oldid=93465“