InhaltsverzeichnisKlicke auf den Link, um zur gewünschten Stelle zu navigieren
Dieser Inhalt wurde automatisch aus dem Ukrainischen übersetzt.
QuickSort ist ein Sortieralgorithmus, der die Strategie "teilen und herrschen" verwendet. Er sortiert Arrays schnell und effizient, indem er Elemente vergleicht und sie an die richtigen Positionen verschiebt.
Wann und von wem wurde QuickSort erstellt?
QuickSort wurde 1959 von dem britischen Ingenieur und Informatiker Tony Hoare entwickelt. Tony Hoare wurde in der Informatik durch seine bedeutenden Beiträge bekannt, und QuickSort wurde zu einer seiner bekanntesten Erfindungen. Tony Hoare erhielt 1980 den Turing Award für seine Arbeiten im Bereich Sortierung und Analyse von Algorithmen.
Wie funktioniert die QuickSort-Sortierung genau?
- Ein Pivot-Element wird ausgewählt. Dies kann jedes Element des Arrays sein, zum Beispiel das erste, letzte oder mittlere Element.
- Die Elemente des Arrays werden so angeordnet, dass alle Elemente, die kleiner als das Pivot sind, vor ihm platziert werden und alle größeren Elemente nach ihm. Das Pivot-Element landet an seiner endgültigen Position.
- QuickSort wird rekursiv auf das Teilarray angewendet, das sich vor dem Pivot-Element befindet (kleinere Elemente) und auf das Teilarray, das sich nach dem Pivot-Element befindet (größere Elemente).
- Die Schritte 1-3 werden für jedes Teilarray wiederholt, bis das gesamte Array sortiert ist.
Da QuickSort die Strategie "teilen und herrschen" anwendet, zeigt er eine gute Geschwindigkeit. Im Durchschnitt hat er eine Komplexität von O(n log n), wobei n die Anzahl der Elemente im Array ist. Im schlimmsten Fall kann die Komplexität O(n^2) betragen, wenn das Pivot-Element immer als das größte oder kleinste Element des Arrays ausgewählt wird. Um den schlimmsten Fall zu vermeiden, können verschiedene Strategien zur Auswahl des Pivot-Elements verwendet werden, wie zum Beispiel zufällige Auswahl oder die Median von drei Elementen.
Beispiel für den QuickSort-Algorithmus (JavaScript).
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[Math.floor(arr.length / 2)];
const less = [];
const greater = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
less.push(arr[i]);
} else if (arr[i] > pivot) {
greater.push(arr[i]);
}
}
return [...quickSort(less), pivot, ...quickSort(greater)];
}
// Beispielverwendung:
const array = [5, 3, 1, 6, 2, 4];
const sortedArray = quickSort(array);
console.log(sortedArray);
Die Funktion quickSort nimmt ein Array arr als Eingabeparameter und gibt ein sortiertes Array zurück.
Der QuickSort-Algorithmus teilt das Eingangsarray rekursiv in kleinere und größere Teilarrays in Bezug auf das gewählte Pivot-Element (pivot). Elemente, die kleiner als pivot sind, werden in less gespeichert, und größere in greater. Dann wird ein rekursiver Aufruf von quickSort für die Teilarrays less und greater gemacht, und die Ergebnisse werden mit dem Pivot-Element pivot kombiniert, um das endgültige sortierte Array zu bilden.
Ergebnis:
[1, 2, 3, 4, 5, 6]
Beispiel für den QuickSort-Algorithmus (Ruby).
def quick_sort(arr)
return arr if arr.length <= 1
pivot = arr[arr.length / 2]
less = []
greater = []
arr.each do |element|
if element < pivot
less << element
elsif element > pivot
greater << element
end
end
return [*quick_sort(less), pivot, *quick_sort(greater)]
end
# Beispielverwendung:
array = [5, 3, 1, 6, 2, 4]
sorted_array = quick_sort(array)
puts sorted_array
Ähnlich wie im JavaScript-Beispiel - die Funktion quick_sort nimmt ein Array arr als Eingabeparameter und gibt ein sortiertes Array zurück.
Der QuickSort-Algorithmus teilt das Eingangsarray rekursiv in kleinere und größere Teilarrays in Bezug auf das gewählte Pivot-Element (pivot). Elemente, die kleiner als pivot sind, werden im Array less gespeichert, und größere im Array greater. Dann wird quick_sort rekursiv für die Teilarrays less und greater aufgerufen, und die Ergebnisse werden mit dem Pivot-Element pivot unter Verwendung des Entpackungsoperators * kombiniert, um das endgültige sortierte Array zu bilden.
Ergebnis:
[1, 2, 3, 4, 5, 6]
Wird der QuickSort-Algorithmus in den Standardmethoden von JavaScript oder Ruby verwendet?
In den Standardmethoden der Programmiersprachen Ruby und JavaScript, die für das Sortieren verantwortlich sind, wird in der Regel nicht der genaue QuickSort-Algorithmus verwendet. Dies kann je nach spezifischer Implementierung der Sprache und ihrer Version sowie je nach einzigartigen Anforderungen und Optimierungen, die verwendet werden, variieren.
In Ruby wird für das Sortieren von Arrays standardmäßig ein Algorithmus verwendet, der Methoden von QuickSort, InsertionSort und HeapSort kombiniert. Dieser Algorithmus wird Timsort genannt, der entwickelt wurde, um verschiedene Datentypen optimal zu sortieren.
In JavaScript wird das Sortieren von Arrays normalerweise mit der Methode Array.prototype.sort() durchgeführt. Die Implementierung dieser Methode kann zwischen verschiedenen JavaScript-Implementierungen (zum Beispiel den V8-Engines in Node.js oder Chrome und SpiderMonkey in Firefox) variieren. In den meisten Fällen wird ein schneller und optimierter Algorithmus verwendet, der QuickSort mit InsertionSort oder MergeSort kombiniert, abhängig von der Implementierung.
Somit, obwohl QuickSort als einer der Komponenten oder grundlegenden Algorithmen in den Sortiermethoden von Ruby und JavaScript verwendet werden kann, ist QuickSort selbst nicht der einzige Algorithmus, der in diesen Sprachen standardmäßig für das Sortieren verwendet wird. In der Regel werden komplexere Algorithmen wie Timsort oder dessen Variationen verwendet, die verschiedene Sortieralgorithmen kombinieren, um Optimierung und ein breites Spektrum an Anwendungsfällen zu gewährleisten.
Dieser Beitrag hat noch keine Ergänzungen vom Autor.
