Knackender Quick-Sort-Algorithmus: Von der Theorie zur Praxis in wenigen Minuten

Quicksort ist einer der schnellsten Sortieralgorithmen. Es nimmt ein Array von Werten, wählt einen der Werte als „Pivot“-Element und verschiebt die anderen Werte so, dass niedrigere Werte links vom Pivot-Element und höhere Werte rechts davon liegen.

Quick Sort gilt als einer der elegantesten und effizientesten Sortieralgorithmen in der Welt der Algorithmen. Im Gegensatz zu einfacheren Algorithmen wie Bubble Sort oder Selection Sort verwendet Quick Sort eine ausgefeilte Divide-and-Conquer-Strategie, die es in der Praxis deutlich schneller macht. Während Merge Sort auch das Divide-and-Conquer-Prinzip verwendet, führt der einzigartige Partitionierungsansatz von Quick Sort häufig zu einer besseren Leistung und Speichernutzung.

Durchschnittliche Zeitkomplexität: O(n log n)

Zeitkomplexität im schlimmsten Fall: O(n²)

Raumkomplexität: O(log n)

Inhaltsverzeichnis

1. Was ist ein Schnellsortierungsalgorithmus?
2. Wie funktioniert die Schnellsortierung?
   • Zeitkomplexität
   • Weltraumkomplexität
3. JavaScript-Implementierung
4. Fazit

Was ist ein Schnellsortierungsalgorithmus?

Quick Sort ist ein hocheffizienter Sortieralgorithmus, der ein „Pivot“-Element aus dem Array auswählt und die anderen Elemente in zwei Unterarrays aufteilt, je nachdem, ob sie kleiner oder größer als der Pivot sind. Im Gegensatz zu Merge Sort, das zuerst teilt und später kombiniert, führt Quick Sort die Sortierung während des Partitionierungsprozesses durch.

Betrachten Sie diesen Vergleich mit anderen Sortieralgorithmen:

Algorithm	Time Complexity (Average)	Space Complexity	In-Place?
Quick Sort	O(n log n)	O(log n)	Yes
Merge Sort	O(n log n)	O(n)	No
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	Yes
Heap Sort	O(n log n)	O(1)	Yes

Wie funktioniert die Schnellsortierung?

Bevor wir uns mit der JavaScript-Implementierung von Schnellsortierungsalgorithmen befassen, gehen wir Schritt für Schritt vor, um zu verstehen, wie der Algorithmus funktioniert, indem wir ein einfaches Zahlenarray in nur vier einfachen Schritten manuell sortieren.

Die Schnellsortierung kann in vier einfache Schritte unterteilt werden:

1. Wählen Sie ein Pivot-Element aus dem Array. Dieses Element kann das erste, das letzte, das mittlere oder sogar ein zufälliges Element aus der Liste/dem Array sein.
2. Ordnen Sie das Array neu an, sodass alle Elemente kleiner als der Pivot auf der linken Seite und alle Elemente größer auf der rechten Seite liegen.
3. Tauschen Sie das Pivot-Element mit dem ersten Element der größeren Werte aus, sodass sich der Pivot in der Mitte befindet.
4. Wenden Sie dieselben Operationen rekursiv auf die Unterarrays links und rechts vom Pivot an.

Wenden wir diese Schritte auf ein echtes Array an. Sollen wir?

Anfängliches Array: [3, 6, 2, 7, 1]

Schritt 1: Wählen Sie einen Pivot

• Der Einfachheit halber wählen wir das letzte Element als Drehpunkt.
• Pivot = 1

Schritt 2: Ordnen Sie das Array um den Drehpunkt herum neu an

• Ordnen Sie es so an, dass alle Elemente kleiner als der Drehpunkt (1) links und alle Elemente größer rechts liegen.
• Während wir jedes Element durchgehen:
  • 3 (größer als 1) → bleibt rechts.
  • 6 (größer als 1) → bleibt rechts.
  • 2 (größer als 1) → bleibt rechts.
  • 7 (größer als 1) → bleibt rechts.
• Neu angeordnetes Array: [1, 6, 2, 7, 3]

Schritt 3: Bringen Sie den Drehpunkt in die richtige Position

• Tauschen Sie den Drehpunkt (1) mit dem ersten Element, das größer als dieser ist, nämlich 6.
• Array nach dem Austausch: [1, 3, 2, 7, 6]
• Jetzt ist 1 an der richtigen Position (Index 0).

Schritt 4: Rekursive Schnellsortierung für Unterarrays

• Linkes Unterarray: [] (von 1 sind keine Elemente übrig, daher gibt es hier nichts zu sortieren)
• Rechtes Unterarray: [3, 2, 7, 6]

---

Rekursives Sortieren des rechten Unterarrays [3, 2, 7, 6].

Schritt 1: Wählen Sie einen Pivot

• Pivot = 6 (letztes Element)

Schritt 2: Ordnen Sie das Array um den Drehpunkt herum neu an

• Ordnen Sie Elemente kleiner als 6 links und größere rechts an:
  • 3 (weniger als 6) → bleibt links.
  • 2 (weniger als 6) → bleibt links.
  • 7 (größer als 6) → bleibt rechts.
• Neu angeordnetes Array: [3, 2, 6, 7]

Schritt 3: Bringen Sie den Drehpunkt in die richtige Position

• 6 befindet sich bereits an der richtigen Position (Index 2).
• Array: [1, 3, 2, 6, 7]

Schritt 4: Rekursive Schnellsortierung für Unterarrays

• Linkes Unterarray: [3, 2]
• Rechtes Unterarray: [7] (einzelnes Element, keine Sortierung erforderlich)

---

Sortieren des linken Subarrays [3, 2]

Schritt 1: Wählen Sie einen Pivot

• Pivot = 2 (letztes Element)

Schritt 2: Ordnen Sie das Array um den Drehpunkt herum neu an

• Neu anordnen, sodass Elemente mit weniger als 2 auf der linken Seite sind:
  • 3 (größer als 2) → bleibt rechts.
• Neu angeordnetes Array: [2, 3]

Schritt 3: Bringen Sie den Drehpunkt in die richtige Position

• 2 befindet sich bereits an der richtigen Position (Index 1).
• Array: [1, 2, 3, 6, 7]

Schritt 4: Rekursive Schnellsortierung für Unterarrays

• Linkes Unterarray: [] (keine Elemente)
• Rechtes Unterarray: [3] (einzelnes Element, keine Sortierung erforderlich)

---

Endgültiges sortiertes Array

Nachdem wir alle Unterarrays sortiert haben, erhalten wir das endgültige sortierte Array:

Sortiertes Array: [1, 2, 3, 6, 7]

Unten finden Sie die beste Veranschaulichung, wie das im wirklichen Leben funktioniert:

Zeitkomplexität

Die zeitliche Komplexität von Quick Sort variiert je nach Pivot-Auswahl:

• Best Case (O(n log n)):

  • Tritt auf, wenn der Pivot das Array immer in gleiche Hälften teilt
  • Ähnlich der Leistung von Merge Sort

• Durchschnittlicher Fall (O(n log n)):

  • Die praktischsten Szenarien
  • Besser als Merge Sort aufgrund der besseren Cache-Auslastung

• Worst Case (O(n²)):

  • Tritt bei bereits sortierten Arrays und schlechter Pivot-Auswahl auf
  • Kann mit guten Pivot-Auswahlstrategien vermieden werden

Weltraumkomplexität

Die Raumkomplexität von Quick Sort beträgt O(log n), weil:

• Rekursive Aufrufstapeltiefe
• In-Place-Partitionierung (im Gegensatz zum zusätzlichen O(n)-Speicherplatz von Merge Sort)
• Bessere Speichereffizienz im Vergleich zu Merge Sort

JavaScript-Implementierung

function quickSort(arr) {
  // Base case: arrays with length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Helper function to swap elements
  const swap = (i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  };

  // Partition function using Lomuto's partition scheme
  function partition(low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(i, j);
      }
    }
    swap(i + 1, high);
    return i + 1;
  }

  // Main quickSort function implementation
  function quickSortHelper(low, high) {
    if (low < high) {
      const pivotIndex = partition(low, high);
      quickSortHelper(low, pivotIndex - 1); // Sort left side
      quickSortHelper(pivotIndex + 1, high); // Sort right side
    }
  }

  quickSortHelper(0, arr.length - 1);
  return arr;
}

Abschluss

Quick Sort ist aufgrund seiner Effizienz und Sortierung vor Ort eine beliebte Wahl. Es übertrifft einfachere Algorithmen wie Bubble Sort und Selection Sort mit seiner O(n log n)-Durchschnittsleistung und der geringen Platzkomplexität.

Wichtige Erkenntnisse:

1. Wählen Sie die Pivot-Auswahlstrategie sorgfältig aus
2. Berücksichtigen Sie Eingabemerkmale, wenn Sie zwischen Quick Sort und anderen Algorithmen entscheiden
3. Verwenden Sie eine zufällige Pivot-Auswahl für eine bessere Durchschnittsleistung

---

---

Bleiben Sie auf dem Laufenden und verbunden

Um sicherzustellen, dass Sie keinen Teil dieser Serie verpassen und um mit mir in Kontakt zu treten, um mehr darüber zu erfahren
Diskussionen über Softwareentwicklung (Web, Server, Mobil oder Scraping/Automatisierung), Daten
Strukturen und Algorithmen und andere spannende Technologiethemen, folgen Sie mir auf:

Emmanuel Ayinde Folgen

Softwareentwickler | Technischer Redakteur | Backend-, Web- und Mobilentwickler? | Leidenschaft für die Entwicklung effizienter und skalierbarer Softwarelösungen. #letsconnect ?

• GitHub
• Linkedin
• X (Twitter)

Bleiben Sie dran und viel Spaß beim Programmieren ?‍??

Das obige ist der detaillierte Inhalt vonKnackender Quick-Sort-Algorithmus: Von der Theorie zur Praxis in wenigen Minuten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!