Wie funktioniert sort() von Javascript?

Lesezeit: 9 Minuten

Wie funktioniert sort von Javascript
cw84

Wie sortiert der folgende Code dieses Array in numerischer Reihenfolge?

var array=[25, 8, 7, 41]

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

Ich weiß, wenn das Ergebnis der Berechnung…

Weniger als 0: “a” wird nach einem niedrigeren Index als “b” sortiert.
Null: “a” und “b” werden als gleich angesehen, und es wird keine Sortierung durchgeführt.
Größer als 0: “b” wird so sortiert, dass es ein niedrigerer Index als “a” ist.

Wird die Array-Sortier-Callback-Funktion im Verlauf der Sortierung viele Male aufgerufen?

Wenn ja, würde ich gerne wissen, welche zwei Zahlen jedes Mal an die Funktion übergeben werden. Ich nahm an, dass es zuerst “25” (a) und “8” (b) brauchte, gefolgt von “7” (a) und “41” (b), also:

25(a) – 8(b) = 17 (größer als Null, also sortiere “b” nach einem niedrigeren Index als “a”): 8, 25

7(a) – 41(b) = -34 (weniger als 0, also sortiere “a” nach einem niedrigeren Index als “b”: 7, 41

Wie werden die beiden Zahlengruppen dann zueinander sortiert?

Bitte helfen Sie einem kämpfenden Neuling!

Wie funktioniert sort von Javascript
OscarRyz

Wird die Array-Sortier-Callback-Funktion im Verlauf der Sortierung viele Male aufgerufen?

Jawohl

Wenn ja, würde ich gerne wissen, welche zwei Zahlen jedes Mal an die Funktion übergeben werden

Du könntest dich selbst herausfinden mit:

array.sort((a,b) => {
  console.log(`comparing ${a},${b}`);
  return a > b ? 1
               : a === b ? 0 
                         : -1;
});

BEARBEITEN

Dies ist die Ausgabe, die ich habe:

25,8
25,7
8,7
25,41

  • mache lieber ein console.log zu firebug oder html DIV element’s .innerHTML += “comparing ” + a + “, ” + b + “\n”;

    – Josua

    29. September 2009 um 20:32 Uhr

  • Denken Sie daran, dass dies eine Wiki-ähnliche Seite ist und wir andere Antworten bearbeiten können, um sie besser zu machen 🙂

    – Pablo Fernández

    9. Juli 2011 um 23:29 Uhr

  • Nur eine Anmerkung zur neuen ES6-Syntax: array.sort((a,b) => a - b); ist gültige Syntax

    – Sterling Archer

    30. November 2015 um 20:12 Uhr

  • Wenn die Sortierfunktion -ve zurückgibt, dann wird getauscht und +ve, dann wird nicht getauscht ??

    – Mahi

    6. Dezember 2016 um 12:27 Uhr

  • @ShekharReddy Sie können immer noch Operatoren zum Vergleichen verwenden. Ich habe die Antwort aktualisiert.

    – Oscar Ryz

    7. März 2018 um 16:38 Uhr

1646318119 947 Wie funktioniert sort von Javascript
Warren Jung

Der JavaScript-Interpreter hat eine Art von Sortieralgorithmus Implementierung eingebaut. Sie ruft die Vergleichsfunktion einige Male während des Sortiervorgangs auf. Wie oft die Vergleichsfunktion aufgerufen wird, hängt vom jeweiligen Algorithmus, den zu sortierenden Daten und der Reihenfolge ab, in der sie sich vor der Sortierung befinden.

Einige Sortieralgorithmen schneiden bei bereits sortierten Listen schlecht ab, da sie dadurch viel mehr Vergleiche anstellen als im typischen Fall. Andere kommen gut mit vorsortierten Listen zurecht, haben aber andere Fälle, in denen sie zu einer schlechten Leistung “ausgetrickst” werden können.

Es gibt viele Sortieralgorithmen, die allgemein verwendet werden, da kein einzelner Algorithmus für alle Zwecke perfekt ist. Die beiden am häufigsten für die generische Sortierung verwendeten sind Schnelle Sorte und Zusammenführen, sortieren. Quicksort ist oft das schnellere der beiden, aber Mergesort hat einige nette Eigenschaften, die es insgesamt zu einer besseren Wahl machen können. Zusammenführungssortierung ist stabil, während Quicksort dies nicht ist. Beide Algorithmen sind parallelisierbar, aber die Art und Weise, wie Mergesort funktioniert, macht eine parallele Implementierung effizienter, wenn alle anderen gleich sind.

Ihr bestimmter JavaScript-Interpreter verwendet möglicherweise einen dieser Algorithmen oder etwas ganz anderes. Die ECMAScript Standard gibt nicht an, welcher Algorithmus eine konforme Implementierung verwenden muss. Sie verleugnet sogar ausdrücklich die Notwendigkeit von Stabilität.

  • FWIW, Basic Quicksort ist einer der Algorithmen, die “ausgetrickst” werden können, um eine schlechte Leistung zu erbringen. In der einfachen Form hat es eine Leistung von O(N^2) für Listen, die entweder bereits sortiert oder genau umgekehrt sind. Die meisten Bibliotheks-Quicksort-Algorithmen verfügen über eine Reihe nicht offensichtlicher Optimierungen, die dazu beitragen, diese häufigen Worst-Case-Szenarien zu vermeiden.

    – Adissak

    29. September 2009 um 20:42 Uhr

  • JavaScriptCore verwendet tatsächlich einen AVL-Baum zum Sortieren, da es notwendig ist, sich angesichts von Komparatorfunktionen, die das zu sortierende Array modifizieren, deterministisch zu verhalten.

    – Oliej

    30. September 2009 um 2:14 Uhr

  • ECMAScript-Standard braucht jetzt Stabilität.

    – ggorlen

    6. Oktober 2020 um 23:06 Uhr

1646318119 526 Wie funktioniert sort von Javascript
Nosredna

Wertepaare werden verglichen, ein Paar nach dem anderen. Die verglichenen Paare sind ein Implementierungsdetail – gehen Sie nicht davon aus, dass sie in jedem Browser gleich sind. Der Rückruf kann alles sein (also können Sie Zeichenfolgen oder römische Ziffern oder irgendetwas anderes sortieren, wo Sie eine Funktion finden können, die 1,0,-1 zurückgibt).

Eine Sache, die Sie bei der Sortierung von JavaScript beachten sollten, ist, dass es nicht garantiert ist, dass sie stabil ist.

Wird die Array-Sortier-Callback-Funktion im Verlauf der Sortierung viele Male aufgerufen?

Ja, genau das ist es. Der Rückruf wird verwendet, um Elementepaare im Array nach Bedarf zu vergleichen, um zu bestimmen, in welcher Reihenfolge sie sein sollten. Diese Implementierung der Vergleichsfunktion ist nicht untypisch, wenn es um eine numerische Sortierung geht. Einzelheiten im die spez oder an etwas andere besser lesbar Websites.

Tiefes Wissen

Bei negativem Ergebnis wird a vor b einsortiert.

Bei positivem Ergebnis wird b vor a einsortiert.

Wenn das Ergebnis 0 ist, werden keine Änderungen an der Sortierreihenfolge der beiden Werte vorgenommen.

HINWEIS:

Dieser Code ist die Ansicht innerhalb der Sortieren Methode Schritt für Schritt.

AUSGANG:

let arr = [90, 1, 20, 14, 3, 55];
var sortRes = [];
var copy = arr.slice();		//create duplicate array
var inc = 0;	//inc meant increment
copy.sort((a, b) => {
	sortRes[inc] = [ a, b, a-b ];
	inc += 1;
	return a - b;
});
var p = 0;
for (var i = 0; i < inc; i++) {
	copy = arr.slice();
	copy.sort((a, b) => {
		p += 1;
		if (p <= i ) {
			return a - b;
		}
		else{
			return false;
		}
	});
	p = 0;
	console.log(copy +' \t a: '+ sortRes[i][0] +' \tb: '+ sortRes[i][1] +'\tTotal: '+ sortRes[i][2]);
}

Zur Klärung des Verhaltens von Array#sort und sein Vergleicher halten dies für naiv Sortieren durch Einfügen in Programmierkursen für Anfänger gelehrt:

const sort = arr => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && arr[j-1] > arr[j]; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array);
console.log("" + array);

Ignorieren Sie die Wahl der Einfügungssortierung als Algorithmus, konzentrieren Sie sich auf die fest codiert Komparator: arr[j-1] > arr[j]. Dies hat zwei Probleme, die für die Diskussion relevant sind:

  1. Die > -Operator wird für Paare von Array-Elementen aufgerufen, aber viele Dinge, die Sie sortieren möchten, wie z. B. Objekte, reagieren nicht > auf vernünftige Weise (dasselbe wäre der Fall, wenn wir verwendet hätten -).
  2. Selbst wenn Sie mit Zahlen arbeiten, möchten Sie oft eine andere Anordnung als die hier eingebrannte aufsteigende Sortierung.

Wir können diese Probleme beheben, indem wir a hinzufügen comparefn Argument, das Sie kennen:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array, (a, b) => a - b);
console.log("" + array);

sort(array, (a, b) => b - a);
console.log("" + array);

const objArray = [{id: "c"}, {id: "a"}, {id: "d"}, {id: "b"}];
sort(objArray, (a, b) => a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray, null, 2));

Nun wird die naive Sortierroutine verallgemeinert. Sie können genau sehen, wann dieser Rückruf aufgerufen wird, und Ihre ersten Bedenken beantworten:

Wird die Array-Sortier-Callback-Funktion im Verlauf der Sortierung viele Male aufgerufen? Wenn ja, würde ich gerne wissen, welche zwei Zahlen jedes Mal an die Funktion übergeben werden

Das Ausführen des folgenden Codes zeigt, dass die Funktion viele Male aufgerufen wird und Sie verwenden können console.log um zu sehen, welche Nummern übergeben wurden:

const sort = (arr, comparefn) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
      [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
    }
  }
};

console.log("on our version:");
const array = [3, 0, 4, 5];
sort(array, (a, b) => console.log(a, b) || (a - b));
console.log("" + array);

console.log("on the builtin:");
console.log("" + 
  [3, 0, 4, 5].sort((a, b) => console.log(a, b) || (a - b))
);

Du fragst:

Wie werden die beiden Zahlengruppen dann zueinander sortiert?

Um mit der Terminologie genau zu sein, a und b sind nicht setzt von Zahlen – sie sind Objekte im Array (in Ihrem Beispiel sind sie Zahlen).

Die Wahrheit ist, es spielt keine Rolle wie sie sind sortiert, weil es implementierungsabhängig ist. Hätte ich einen anderen Sortieralgorithmus als Insertion Sort verwendet, würde der Komparator wahrscheinlich für andere Zahlenpaare aufgerufen werden, aber am Ende des Sortieraufrufs ist die Invariante, die für den JS-Programmierer wichtig ist, dass das Ergebnisarray entsprechend sortiert wird Komparator, vorausgesetzt, der Komparator gibt Werte zurück, die dem von Ihnen angegebenen Vertrag entsprechen (< 0, wenn a < b0 wenn a === b und > 0 wenn a > b).

In dem gleichen Sinne, in dem ich die Freiheit habe, die Implementierung meiner Art zu ändern, solange ich nicht gegen meine Spezifikation verstoße, können Implementierungen von ECMAScript die Implementierung von Sort innerhalb der Grenzen von frei wählen Sprachspezifikationdamit Array#sort wird wahrscheinlich unterschiedliche Komparatoraufrufe auf verschiedenen Engines erzeugen. Man würde keinen Code schreiben, bei dem die Logik auf einer bestimmten Abfolge von Vergleichen beruht (noch sollte der Komparator überhaupt Nebeneffekte erzeugen).

Zum Beispiel ruft der V8-Motor (zum Zeitpunkt des Schreibens) auf Timsort wenn das Array größer als eine vorberechnete Anzahl von Elementen ist und a verwendet binäre Einfügungssortierung für kleine Array-Chunks. Es wurde jedoch verwendet schnelle Sorte was instabil ist und dem Komparator wahrscheinlich eine andere Abfolge von Argumenten und Aufrufen geben würde.

Da verschiedene Sortierimplementierungen den Rückgabewert der Komparatorfunktion unterschiedlich verwenden, kann dies zu überraschendem Verhalten führen, wenn sich der Komparator nicht an den Vertrag hält. Siehe diesen Thread für ein Beispiel.

Wird die Array-Sortier-Callback-Funktion im Verlauf der Sortierung viele Male aufgerufen?

Da dies eine Vergleichssortierung ist, sollte die Callback-Funktion bei gegebenen N Elementen im Durchschnitt (N * Lg N) Mal für eine schnelle Sortierung wie aufgerufen werden Schnelle Sorte. Wenn der verwendete Algorithmus so etwas wie Blasensortierungdann wird die Callback-Funktion durchschnittlich (N * N) mal aufgerufen.

Die minimale Anzahl von Aufrufen für eine Vergleichssortierung ist (N-1), und dies dient nur dazu, eine bereits sortierte Liste zu erkennen (dh früh außerhalb der Blasensortierung, wenn keine Austauschvorgänge stattfinden).

924380cookie-checkWie funktioniert sort() von Javascript?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy