Stabile `Array.prototype.sort`
Angenommen, Sie haben ein Array von Hunden, wobei jeder Hund einen Namen und eine Bewertung hat. (Falls dies wie ein seltsames Beispiel klingt, sollten Sie wissen, dass es ein Twitter-Konto gibt, das sich genau darauf spezialisiert hat… Fragen Sie nicht!)
// Beachten Sie, dass das Array nach `name` alphabetisch vorsortiert ist.
const doggos = [
{ name: 'Abby', rating: 12 },
{ name: 'Bandit', rating: 13 },
{ name: 'Choco', rating: 14 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
{ name: 'Falco', rating: 13 },
{ name: 'Ghost', rating: 14 },
];
// Sortieren Sie die Hunde nach `rating` in absteigender Reihenfolge.
// (Dies aktualisiert `doggos` direkt.)
doggos.sort((a, b) => b.rating - a.rating);
Das Array ist alphabetisch nach Namen vorsortiert. Um stattdessen nach Bewertung zu sortieren (sodass die Hunde mit der höchsten Bewertung zuerst kommen), verwenden wir Array#sort und geben eine benutzerdefinierte Rückruffunktion weiter, die die Bewertungen vergleicht. Dies ist das Ergebnis, das Sie wahrscheinlich erwarten würden:
[
{ name: 'Choco', rating: 14 },
{ name: 'Ghost', rating: 14 },
{ name: 'Bandit', rating: 13 },
{ name: 'Falco', rating: 13 },
{ name: 'Abby', rating: 12 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
]
Die Hunde sind nach Bewertung sortiert, aber innerhalb jeder Bewertung sind sie weiterhin alphabetisch nach Namen sortiert. Zum Beispiel haben Choco und Ghost dieselbe Bewertung von 14, aber Choco erscheint im Sortierergebnis vor Ghost, da dies ebenfalls die Reihenfolge im ursprünglichen Array war.
Um dieses Ergebnis zu erhalten, kann die JavaScript-Engine jedoch nicht irgendeinen Sortieralgorithmus verwenden – es muss ein sogenannter „stabiler Sortieralgorithmus“ sein. Lange Zeit verlangte die JavaScript-Spezifikation keine Stabilität für Array#sort und überließ es den Implementierungen. Da dieses Verhalten nicht spezifiziert war, hätten Sie auch dieses Sortierergebnis erhalten können, bei dem Ghost plötzlich vor Choco erscheint:
[
{ name: 'Ghost', rating: 14 }, // 😢
{ name: 'Choco', rating: 14 }, // 😢
{ name: 'Bandit', rating: 13 },
{ name: 'Falco', rating: 13 },
{ name: 'Abby', rating: 12 },
{ name: 'Daisy', rating: 12 },
{ name: 'Elmo', rating: 12 },
]
Mit anderen Worten: JavaScript-Entwickler konnten sich nicht auf Sortierstabilität verlassen. Praktisch war die Situation noch frustrierender, da einige JavaScript-Engines einen stabilen Sortieralgorithmus für kurze Arrays und einen instabilen Sortieralgorithmus für größere Arrays verwendeten. Dies war wirklich verwirrend, da Entwickler ihren Code testeten, ein stabiles Ergebnis sahen, aber plötzlich ein instabiles Ergebnis in der Produktion erhielten, wenn das Array etwas größer war.
Aber es gibt gute Nachrichten. Wir haben eine Änderung an der Spezifikation vorgeschlagen, die Array#sort stabil macht, und sie wurde akzeptiert. Alle großen JavaScript-Engines implementieren nun eine stabile Array#sort. Eine Sorge weniger für JavaScript-Entwickler. Schön!
(Oh, und wir haben dasselbe für TypedArrays gemacht: Auch diese Sortierung ist jetzt stabil.)
Hinweis: Obwohl Stabilität nun gemäß Spezifikation erforderlich ist, sind JavaScript-Engines weiterhin frei, jeden beliebigen Sortieralgorithmus zu implementieren. V8 verwendet Timsort, zum Beispiel. Die Spezifikation schreibt keinen bestimmten Sortieralgorithmus vor.