Algorithmen und Datenstrukturen · Middle · Frage 4 von 75
Warum ist Quicksort in der Praxis oft schneller als Merge Sort, trotz gleichem Durchschnitt O(n log n)?
- 1Es ist stabil und muss gleiche Elemente daher nicht bewegen
- 2Es macht im schlimmsten Fall weniger Vergleiche
- 3Es sortiert an Ort und Stelle und greift sequenziell auf Speicher zu
Antwort zeigen
Richtige Antwort: Es sortiert an Ort und Stelle und greift sequenziell auf Speicher zu
Erklärung
Das Aufteilen arbeitet im Array mit guter Cache-Lokalität und kleinen Konstanten. Sein schlimmster Fall ist sogar schlechter (O(n²)), und die übliche In-place-Version ist nicht stabil.