Was ist quicksort?

Quicksort

Quicksort ist ein effizienter, generischer Algorithmus zum Sortieren. Er folgt dem Prinzip Teile und Herrsche, um eine Liste zu sortieren.

Kernprinzip:

1. Auswahl eines Pivots: Ein Element aus der Liste wird als Pivot ausgewählt. Die Wahl des Pivots kann die Effizienz des Algorithmus stark beeinflussen.
2. Partitionierung: Die Liste wird so umgeordnet, dass alle Elemente, die kleiner als der Pivot sind, vor dem Pivot platziert werden, und alle Elemente, die größer als der Pivot sind, nach dem Pivot. Nach dieser Partitionierung befindet sich der Pivot an seiner endgültigen Position.
3. Rekursion: Die Sub-Listen links und rechts des Pivots werden rekursiv mit Quicksort sortiert.

Schritte im Detail:

• Pivot-Auswahl: (Pivot-Auswahl) Es gibt verschiedene Strategien zur Auswahl des Pivots. Häufige Methoden sind:

  • Erstes Element
  • Letztes Element
  • Mittleres Element
  • Zufälliges Element
  • Median-of-Three

• Partitionierung: (Partitionierung) Es gibt verschiedene Partitionierungsalgorithmen. Ein verbreiteter Ansatz ist der Lomuto-Partitionierungsalgorithmus oder der Hoare-Partitionierungsalgorithmus. Ziel ist es, alle Elemente kleiner als das Pivot nach links und alle Elemente größer als das Pivot nach rechts zu verschieben.

• Rekursiver Aufruf: (Rekursiver%20Aufruf) Quicksort wird rekursiv auf die beiden Sub-Listen angewendet, bis die Sub-Listen eine Länge von 0 oder 1 haben (da diese bereits sortiert sind).

Komplexität:

• Best-Case: O(n log n)
• Average-Case: O(n log n)
• Worst-Case: O(n^2) (tritt auf, wenn das Pivot wiederholt schlecht gewählt wird, z.B. immer das kleinste oder größte Element)
• Space-Komplexität: O(log n) im Durchschnitt (aufgrund der rekursiven Aufrufe), O(n) im schlechtesten Fall (wenn die Rekursionstiefe linear mit der Eingabegröße wächst).

Vorteile:

• Sehr effizient im Durchschnitt
• In-Place-Sortierung (benötigt nur wenig zusätzlichen Speicherplatz)

Nachteile:

• Schlechteste Fall-Performance ist quadratisch.
• Nicht stabil (die relative Reihenfolge gleicher Elemente kann sich ändern).

Verbesserungen:

• Randomisierte Pivot-Auswahl: Hilft, den Worst-Case zu vermeiden.
• Insertion Sort für kleine Sub-Listen: Für kleine Sub-Listen ist Insertion Sort oft effizienter als Quicksort.
• Three-Way-Partitionierung: Behandelt Duplikate effizienter.

Anwendungen:

Quicksort wird häufig in Sortierbibliotheken und -funktionen verwendet, insbesondere wenn Geschwindigkeit wichtig ist und In-Place-Sortierung bevorzugt wird. Es eignet sich gut für große Datensätze.