Który z wymienionych algorytmów sortujących posiada średnią złożoność obliczeniową równą O(n log n)?
QuickSort to naprawdę jeden z najlepszych sposobów na sortowanie. W zasadzie chodzi o to, że dzielimy naszą tablicę na dwie części, z pomocą takiego specjalnego elementu, który nazywamy pivotem. W praktyce działa to tak, że mamy część mniejszą i większą od tego pivota, a potem każdą z tych części sortujemy jeszcze raz, tak jakbyśmy powtarzali cały proces. Myślę, że to działa super, szczególnie na dużych zbiorach danych, i dlatego QuickSort jest naprawdę popularny w różnych programach i aplikacjach.
Sortowanie przez wstawianie jest dość powolne, z tą złożonością O(n²). W zasadzie fajnie sprawdza się tylko w małych zbiorach lub gdy tablica już jest mniej więcej posortowana. A jeśli chodzi o sortowanie bąbelkowe, to chyba nie ma co się łudzić, jest jednym z najgorszych algorytmów, też O(n²). I sortowanie przez wybór? Tutaj też nie ma rewelacji, bo porównuje się i wybiera najmniejszy element w każdej iteracji, co znacznie spowalnia działanie, zwłaszcza przy dużych tablicach. Tak że generalnie, lepiej unikać tych algorytmów, jeśli to możliwe.