QuickSort-Algorithmus in JavaSkript

Was ist Sortieren?

Sortieren ist nichts anderes als das Anordnen von Elementen in der gewünschten Reihenfolge. Vielleicht sind Sie in Ihrer Schul- oder Collegezeit schon einmal darauf gestoßen. So wie das Anordnen von Zahlen von klein nach groß (aufsteigend) oder von groß nach klein (absteigend) ist, was wir bisher gesehen haben, und wird Sortieren genannt.

Standardsortierung in JavaSkript

Wie bereits erwähnt, JavaSkript hat Sortieren(). Nehmen wir ein Beispiel mit wenigen Array-Elementen wie [5,3,7,6,2,9] und möchten diese Array-Elemente in aufsteigender Reihenfolge sortieren. Ruf einfach an Sortieren() auf dem Array „items“ und sortiert 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, die Schnellsortierung anstelle der Standardsortierung () zu wählen? JavaSkript

Obwohl sort() das gewünschte Ergebnis liefert, liegt das Problem in der Art und Weise, wie die Array-Elemente sortiert werden. Standardmäßig wird sort() in JavaSkript verwendet Sortieren durch Einfügen by V8-Motor aus Chrom und Zusammenführen, sortieren by Mozilla Firefox und Safari.

Ansonsten 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 Datensätze zu verwenden.

Um es vollständig zu verstehen, müssen Sie also wissen, wie die Schnellsortierung funktioniert, und lassen Sie uns das jetzt im Detail sehen.

Was ist Schnellsortierung?

Es folgt eine schnelle Sortierung Teilen und Erobern Algorithmus. Er teilt Elemente basierend auf bestimmten Bedingungen in kleinere Teile auf und führt die Sortiervorgänge für diese aufgeteilten kleineren Teile aus. Daher funktioniert er gut für große Datensätze. Hier sind also die Schritte, wie Quicksort in einfachen Worten funktioniert.

1. Wählen Sie zunächst ein Element aus, das aufgerufen werden soll Drehpunkt Element.
2. Vergleichen Sie als Nächstes alle Array-Elemente mit dem ausgewählten Pivot-Element und ordnen Sie sie so an, dass sich Elemente, die kleiner als das Pivot-Element sind, links davon und Elemente, die größer als das Pivot-Element sind, rechts davon befinden.
3. Führen Sie abschließend die gleichen Vorgänge an den linken und rechten Elementen des Pivot-Elements durch.

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

Wie funktioniert QuickSort?

1. Finden Sie zuerst die „drehen“ Element im Array.
2. Starten Sie den linken Zeiger beim ersten Element des Arrays.
3. Starten Sie den rechten Zeiger beim letzten Element des Arrays.
4. Vergleichen Sie das zeigende 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 damit fort, bis das linke Seitenelement größer oder gleich dem Pivotelement ist.
5. Vergleichen Sie das zeigende Element 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 damit fort, bis das rechte Seitenelement kleiner oder gleich dem Pivotelement ist.
6. Überprüfen Sie, ob der linke Zeiger kleiner oder gleich dem rechten Zeiger ist, und tauschen Sie dann die Elemente an den Positionen dieser Zeiger aus.
7. Erhöhen Sie den linken Zeiger und verringern Sie den rechten Zeiger.
8. 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.

Sehen wir uns diese Schritte also anhand eines Beispiels an. Betrachten wir das Array der Elemente, die wir sortieren müssen, als [5,3,7,6,2,9].

Pivot-Element bestimmen

Doch bevor wir 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 machen dasselbe.

Hier sind die Schritte zur Durchführung der Schnellsortierung, die anhand eines Beispiels [5,3,7,6,2,9] gezeigt werden.

SCHRITTE: Drehpunkt als mittleres Element festlegen. Also, 7 ist das Drehelement.

SCHRITTE: Beginnen Sie mit dem linken und rechten Zeiger als erstes bzw. letztes Element des Arrays. Der linke Zeiger zeigt also auf 5 am Index 0 und der rechte Zeiger zeigt darauf 9 bei Index 5.

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

SCHRITTE: Jetzt ist es immer noch 3 < 6, also verschieben Sie den linken Zeiger um einen Index weiter nach rechts. Jetzt ist es also 7 > 6, also hören Sie auf, den linken Zeiger zu erhöhen, und jetzt ist der linke Zeiger bei Index 2.

SCHRITTE: Vergleichen Sie nun den Wert am rechten Zeiger mit dem Pivot-Element. Da 9 > 6 ist, bewegen Sie den rechten Zeiger nach links. Da nun 2 < 6 ist, hören Sie auf, den rechten Zeiger zu bewegen.

SCHRITTE: Vertauschen Sie beide am linken und rechten Zeiger vorhandenen Werte miteinander.

SCHRITTE: Bewegen Sie beide Zeiger um einen weiteren Schritt.

SCHRITTE: Da 6 = 6, bewegen Sie die Zeiger um einen weiteren Schritt und stoppen Sie, wenn der linke Zeiger den rechten Zeiger kreuzt, und geben Sie den Index des linken Zeigers zurück.

Basierend auf dem obigen Ansatz müssen wir hier also Code zum Austauschen von Elementen und zum Partitionieren des Arrays schreiben, wie in den obigen Schritten beschrieben.

Code zum Vertauschen von zwei Zahlen in JavaSkript

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

Code zum Durchführen der Partitionierung wie in den obigen Schritten beschrieben

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //swap two elements
            i++;
            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 ihn verwenden, um das Array zu teilen und die Schnellsortierung für diesen Teil durchzuführen. Daher wird es „Divide and Conquer“-Algorithmus genannt.

Daher wird die Schnellsortierung durchgeführt, bis alle Elemente im linken und rechten Array sortiert sind.

Hinweis: Die Schnellsortierung wird für dasselbe Array durchgeführt und dabei werden keine neuen Arrays erstellt.

Also müssen wir das nennen partition () oben erklärt und auf dieser Grundlage teilen wir die Array in Teile. 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 partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var result = quickSort(items, 0, items.length - 1);

Vollständiger Schnellsortierungscode

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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

Anmerkungen: Quicksort läuft mit der Zeitkomplexität von O(nlogn).