Inhaltsverzeichnis:
Definition - Was bedeutet Quicksort?
Quicksort ist ein beliebter Sortieralgorithmus, der in der Praxis häufig schneller ist als andere Sortieralgorithmen. Es verwendet eine Divide-and-Conquer-Strategie, um Datenelemente schnell zu sortieren, indem ein großes Array in zwei kleinere Arrays aufgeteilt wird. Es wurde 1960 von Charles Antony Richard Hoare (allgemein bekannt als CAR Hoare oder Tony Hoare) für ein Projekt zur maschinellen Übersetzung für das National Physical Laboratory entwickelt.Techopedia erklärt Quicksort
Quicksort ist ein Algorithmus, mit dem Elemente innerhalb eines Arrays schnell sortiert werden, unabhängig davon, wie groß das Array ist. Es ist ziemlich skalierbar und funktioniert relativ gut für kleine und große Datenmengen und ist einfach mit wenig Zeitaufwand zu implementieren. Dies geschieht durch eine Divide-and-Conquer-Methode, die ein einzelnes großes Array in zwei kleinere unterteilt und diesen Vorgang für alle erstellten Arrays wiederholt, bis die Sortierung abgeschlossen ist.
Der Quicksort-Algorithmus wird wie folgt ausgeführt:
- Ein Drehpunkt wird aus dem Array ausgewählt.
- Das Array wird neu angeordnet, sodass alle Werte, die kleiner als der Pivot sind, vor und alle Werte, die größer als der Pivot sind, nach dem Array verschoben werden, wobei Werte gleich dem Pivot sind. Wenn dies erfolgt ist, befindet sich der Drehzapfen in seiner Endposition.
- Der obige Schritt wird sowohl für jedes Subarray mit kleineren Werten als auch für das Subarray mit größeren Werten separat wiederholt.
Dies wird wiederholt, bis das gesamte Array sortiert ist.
