QuickSort-Algorithmus in JavaScript

Was ist eine schnelle Sortierung?

Der Quick Sort- Algorithmus folgt dem Divide and Conquer-Ansatz. Es unterteilt Elemente basierend auf bestimmten Bedingungen in kleinere Teile und führt die Sortiervorgänge für diese geteilten kleineren Teile aus.

Der Quick Sort-Algorithmus ist einer der am häufigsten verwendeten und beliebtesten Algorithmen in jeder Programmiersprache. Wenn Sie jedoch ein JavaScript-Entwickler sind, haben Sie möglicherweise von sort () gehört, das bereits in JavaScript verfügbar ist. Dann haben Sie vielleicht darüber nachgedacht, was die Notwendigkeit dieses Schnellsortierungsalgorithmus ist. Um dies zu verstehen, benötigen wir zunächst die Sortierung und die Standardsortierung in JavaScript.

Was ist Sortieren?

Sortieren ist nichts anderes als das Anordnen von Elementen in der gewünschten Reihenfolge. Möglicherweise sind Sie in Ihrer Schul- oder Collegezeit darauf gestoßen. Wie das Anordnen von Zahlen von kleiner nach größer (aufsteigend) oder von größer nach kleiner (absteigend) ist das, was wir bisher gesehen haben und als Sortieren bezeichnet werden.

Standardsortierung in JavaScript

Wie bereits erwähnt, hat JavaScript sort () . Nehmen wir ein Beispiel mit wenigen Arrays von Elementen wie [5,3,7,6,2,9] und möchten diese Array-Elemente in aufsteigender Reihenfolge sortieren. Rufen Sie einfach sort () für das Array "items" auf und sortieren Sie die Array-Elemente in aufsteigender Reihenfolge.

Code:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

Was ist der Grund, in JavaScript Schnellsortierung anstelle von Standardsortierung () zu wählen?

Obwohl sort () das gewünschte Ergebnis liefert, liegt das Problem in der Art und Weise, wie die Array-Elemente sortiert werden. Die Standardeinstellung sort () in JavaScript verwendet die Einfügesortierung nach V8 Engine von Chrome und die Zusammenführungssortierung nach Mozilla Firefox und Safari .

Andernfalls ist dies jedoch nicht geeignet, wenn Sie eine große Anzahl von Elementen sortieren müssen. Die Lösung besteht also darin, die Schnellsortierung für große Datenmengen zu verwenden.

Um dies vollständig zu verstehen, müssen Sie wissen, wie die schnelle Sortierung funktioniert, und das jetzt im Detail sehen.

Was ist eine schnelle Sortierung?

Die schnelle Sortierung folgt dem Divide and Conquer- Algorithmus. Es unterteilt Elemente basierend auf bestimmten Bedingungen in kleinere Teile und führt die Sortieroperationen für diese geteilten kleineren Teile durch. Daher funktioniert es gut für große Datenmengen. Hier sind die Schritte, wie die schnelle Sortierung in einfachen Worten funktioniert.

Wählen Sie zunächst ein Element aus, das als Pivot- Element bezeichnet werden soll.
Vergleichen Sie anschließend alle Array-Elemente mit dem ausgewählten Pivot-Element und ordnen Sie sie so an, dass Elemente, die kleiner als das Pivot-Element sind, links und größer als Pivot rechts sind.
Führen Sie schließlich die gleichen Operationen an den Elementen der linken und rechten Seite des Schwenkelements aus.

Das ist also der Grundriss der Schnellsortierung. Hier sind die Schritte, die einzeln ausgeführt werden müssen, um eine schnelle Sortierung durchzuführen.

Wie funktioniert QuickSort?

Suchen Sie zuerst das "Pivot" -Element im Array.
Starten Sie den linken Zeiger am ersten Element des Arrays.
Starten Sie den rechten Zeiger am letzten Element des Arrays.
Vergleichen Sie das Element mit dem linken Zeiger. Wenn es kleiner als das Pivot-Element ist, bewegen Sie den linken Zeiger nach rechts (addieren Sie 1 zum linken Index). Fahren Sie so fort, bis das linke Seitenelement größer oder gleich dem Schwenkelement ist.
Vergleichen Sie das Element, das zeigt, mit dem rechten Zeiger. Wenn es größer als das Pivot-Element ist, bewegen Sie den rechten Zeiger nach links (subtrahieren Sie 1 vom rechten Index). Fahren Sie so fort, bis das rechte Element kleiner oder gleich dem Schwenkelement ist.
Überprüfen Sie, ob der linke Zeiger kleiner oder gleich dem rechten Zeiger ist, und sehen Sie dann die Elemente an den Positionen dieser Zeiger.
Inkrementieren Sie den linken Zeiger und dekrementieren Sie den rechten Zeiger.
Wenn der Index des linken Zeigers immer noch kleiner als der Index des rechten Zeigers ist, wiederholen Sie den Vorgang. Andernfalls wird der Index des linken Zeigers zurückgegeben.

Lassen Sie uns diese Schritte anhand eines Beispiels betrachten. Betrachten wir eine Reihe von Elementen, die wir sortieren müssen, als [5,3,7,6,2,9].

Pivot-Element bestimmen

Bevor Sie jedoch mit der Schnellsortierung fortfahren, spielt die Auswahl des Pivot-Elements eine wichtige Rolle. Wenn Sie das erste Element als Pivot-Element auswählen, ist die Leistung im sortierten Array am schlechtesten. Daher ist es immer ratsam, das mittlere Element (Länge des Arrays geteilt durch 2) als Pivot-Element auszuwählen, und wir tun dasselbe.

Hier sind die Schritte zum Ausführen der Schnellsortierung, die anhand eines Beispiels gezeigt werden [5,3,7,6,2,9].

SCHRITT 1: Bestimmen Sie den Drehpunkt als mittleres Element. So 7 ist das Schwenkelement.

SCHRITT 2: Starten Sie den linken und rechten Zeiger als erstes bzw. letztes Element des Arrays. Der linke Zeiger zeigt also auf 5 bei Index 0 und der rechte Zeiger zeigt auf 9 bei Index 5.

SCHRITT 3: Vergleichen Sie das Element am linken Zeiger mit dem Pivot-Element. Da 5 <6 den linken Zeiger nach rechts zum Index 1 verschieben.

SCHRITT 4: Jetzt noch 3 <6, also den linken Zeiger auf einen weiteren Index nach rechts verschieben. Jetzt hören 7> 6 auf, den linken Zeiger zu erhöhen, und jetzt befindet sich der linke Zeiger auf Index 2.

SCHRITT 5: Vergleichen Sie nun den Wert am rechten Zeiger mit dem Pivot-Element. Seit 9> 6 bewegen Sie den rechten Zeiger nach links. Wenn 2 <6 ist, bewegen Sie den rechten Zeiger nicht mehr.

SCHRITT 6: Tauschen Sie beide am linken und rechten Zeiger vorhandenen Werte miteinander aus.

SCHRITT 7: Bewegen Sie beide Zeiger noch einen Schritt weiter.

SCHRITT 8: Da 6 = 6, bewegen Sie die Zeiger auf einen weiteren Schritt und halten Sie an, wenn der linke Zeiger den rechten Zeiger kreuzt und den Index des linken Zeigers zurückgibt.

Basierend auf dem obigen Ansatz müssen wir hier Code schreiben, um Elemente auszutauschen und das Array zu partitionieren, wie in den obigen Schritten erwähnt.

Code zum Austauschen von zwei Zahlen in JavaScript:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Code zum Ausführen der Partition wie in den obigen Schritten beschrieben:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Führen Sie die rekursive Operation aus

Sobald Sie die obigen Schritte ausgeführt haben, wird der Index des linken Zeigers zurückgegeben, und wir müssen diesen verwenden, um das Array zu teilen und die Schnellsortierung für diesen Teil durchzuführen. Daher wird es als Divide and Conquer-Algorithmus bezeichnet.

Die schnelle Sortierung wird also durchgeführt, bis alle Elemente im linken und rechten Array sortiert sind.

Hinweis: Die schnelle Sortierung wird für dasselbe Array durchgeführt, und es werden keine neuen Arrays erstellt.

Wir müssen diese oben erläuterte Partition () aufrufen und darauf basierend das Array in Teile aufteilen. Hier ist also der Code, in dem Sie ihn verwenden:

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Vollständiger schneller Sortiercode:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]