Algorytmy i struktury danych · Middle · Pytanie 4 z 75
Dlaczego quicksort jest w praktyce często szybszy od sortowania przez scalanie, choć oba mają średnio O(n log n)?
- 1Jest stabilny, więc nie przenosi równych elementów
- 2Wykonuje mniej porównań w najgorszym przypadku
- ✓Poprawna odpowiedź: Sortuje w miejscu i odczytuje pamięć sekwencyjnie
Wyjaśnienie
Podział działa wewnątrz tablicy z dobrą lokalnością pamięci podręcznej i małymi stałymi. Jego najgorszy przypadek jest w rzeczywistości gorszy (O(n²)), a zwykła wersja w miejscu nie jest stabilna.