Erlernen des Schnellsortierungsalgorithmus

Quick Sort ist einer der effizientesten Algorithmen und verwendet die Divide-and-Conquer-Technik zum Sortieren von Arrays.

So funktioniert die Schnellsortierung

Die Hauptidee von Quick Sort besteht darin, einem Element nach dem anderen dabei zu helfen, an die richtige Position in einem unsortierten Array zu gelangen. Dieses Element wird Pivot genannt.

Das Drehelement befindet sich in der richtigen Position, wenn:

1. Alle Elemente links davon sind kleiner.
2. Alle Elemente rechts davon sind größer.

Es spielt keine Rolle, ob die Zahlen links oder rechts schon sortiert sind. Wichtig ist, dass sich der Drehpunkt an der richtigen Position im Array befindet.

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

All dies sind gültige Ausgaben eines Arrays, bei dem der Pivot 23 ist.

Die richtige Position des Drehpunkts finden

Quick Sort hilft dem Pivot, seine richtige Position im Array zu finden. Wenn sich der Pivot beispielsweise am Anfang des Arrays befindet, aber nicht die kleinste Zahl ist, bestimmt Quick Sort, dass er sich um 5 Schritte bewegen muss, um Platz für die 5 kleineren Elemente im Array zu schaffen – vorausgesetzt, es gibt 5 solcher Elemente Zahlen.

Nehmen wir an, wir haben das Array: [10, 4, 15, 6, 23, 40, 1, 17, 7, 8] und 10 ist der Drehpunkt:

An diesem Punkt:

• Die Nummer 10 weiß nicht, ob sie sich an der richtigen Position befindet und wie viele Schritte sie zurücklegen muss, um dorthin zu gelangen. Quick Sort beginnt mit dem Vergleich von 10 mit dem Wert am nächsten Index.
• Wenn Quick Sort erkennt, dass 4 kleiner ist, zeichnet es auf, dass sich der Pivot einen Schritt nach vorne bewegen muss, damit 4 davor kommen kann.
• Also numberOfStepsToMove erhöht sich um 1.

Als nächstes beträgt der Wert bei Index 2 15, was größer als 10 ist. Da keine Anpassung erforderlich ist, Schnellsortierung behält die Schrittanzahl unverändert bei und geht zum nächsten Element im Array über.

Beim nächsten Index ist der Wert 6, was kleiner als 10 ist. Quick Sort erhöht die Schrittzahl auf 2, da der Pivot nun Platz für zwei kleinere Zahlen schaffen muss: 4 und 6 .

Jetzt muss 6 durch 15 ersetzt werden, damit die kleineren Zahlen auf der linken Seite des Arrays nebeneinander bleiben. Wir tauschen die Zahlen basierend auf den aktuellen Index- und numberOfStepsToMove-Werten aus.

Quick Sort durchläuft weiterhin das Array und erhöht die Zahl „NumberOfStepsToMove“ basierend darauf, wie viele Zahlen kleiner als der Pivot sind. Dadurch lässt sich ermitteln, wie weit sich der Drehpunkt in die richtige Position bewegen muss.

Die numberOfStepsToMove ändert sich bei 23 oder 40 nicht, da beide Werte größer als der Pivot sind und im Array nicht davor stehen sollten:

Wenn Quick Sort nun eine Schleife zum Wert 1 an Index 6 durchläuft, erhöht sich numberOfStepsToMove auf 3 und tauscht die Zahl an Index 3 aus:

Quick Sort setzt diesen Vorgang fort, bis das Ende des Arrays erreicht ist:

Da wir nun das Ende des Arrays erreicht haben, wissen wir, dass es 5 Zahlen gibt, die kleiner als 10 sind. Daher muss sich der Drehpunkt (10) 5 Schritte nach vorne zu seiner richtigen Position bewegen, wo er größer als alle ist Zahlen davor.

Mal sehen, wie das im Code aussieht:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

Da wir nun eine Funktion haben, die uns hilft, die Position des Pivots zu finden, sehen wir uns an, wie Qucik Sort das Array in kleinere Arrays aufteilt und die Funktion getNumberOfStepsToMove verwendet, um alle Array-Elemente zu platzieren.

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i <= end; i++) {
    // is the current number less than the pivot?
    if (arr[i] < pivot) {
      // yes - so w should increase numberOfStepsToMove
// or the new index of the pivot
      numberOfStepsToMove++;

      // now swap the number at the index of numberOfStepsToMove with the smaller one
      [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]];
    } else {
      // what if it's greater?
      // do nothing -- we need to move on to the next number
      // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not
    }
  }

  // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove
  // so we swap the numbers to place the pivot number to its correct position
  [arr[start], arr[numberOfStepsToMove]] = [
    arr[numberOfStepsToMove],
    arr[start],
  ];

  return numberOfStepsToMove;
};

Schnellsortierung nutzt Rekursion, um das Array effizient in kleinere Unterarrays zu unterteilen und sicherzustellen, dass Elemente sortiert werden, indem sie mit einem Pivot verglichen werden.

function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}

• Der Algorithmus sortiert rekursiv das linke Subarray, das Elemente enthält, die kleiner als der Pivot sind.
• Die Rekursion stoppt, wenn das Subarray ein oder kein Element enthält, da es bereits sortiert ist.

Jetzt müssen wir den gleichen Vorgang auf der rechten Seite des Arrays durchführen:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

In diesem Beispiel ist die rechte Seite bereits sortiert, aber der Algorithmus weiß das nicht und sie wäre sortiert worden, wenn dies nicht der Fall gewesen wäre.

Das obige ist der detaillierte Inhalt vonErlernen des Schnellsortierungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!