Który z poniższych algorytmów sortowania charakteryzuje się średnią złożonością obliczeniową O(n log n)?
Odpowiedzi
Informacja zwrotna
QuickSort to jeden z najefektywniejszych algorytmów sortowania o średniej złożoności O(n log n). Działa na zasadzie 'dziel i zwyciężaj', wybierając element zwany pivotem i dzieląc tablicę na dwie części – mniejszą od pivota i większą od pivota. Następnie każda z tych części jest sortowana rekurencyjnie. QuickSort jest niezwykle szybki w praktyce i działa dobrze na dużych zbiorach danych, co czyni go jednym z najczęściej wykorzystywanych algorytmów sortowania w aplikacjach produkcyjnych.
Sortowanie przez wstawianie ma złożoność O(n²) i jest efektywne tylko dla małych zbiorów danych lub tablic, które są wstępnie posortowane. Sortowanie bąbelkowe również ma złożoność O(n²) i jest jednym z najmniej efektywnych algorytmów sortowania. Sortowanie przez wybór (Selection Sort) również działa w czasie O(n²), porównując i wybierając najmniejszy element w każdej iteracji, co czyni go powolnym dla dużych tablic.