Który z wymienionych algorytmów działających na tablicy jednowymiarowej ma złożoność obliczeniową \( O(n^2) \)?
Sortowanie bąbelkowe to taki klasyczny algorytm, który ma złożoność \( O(n^2) \). Chociaż jest dość prosty w zrozumieniu, to nie za bardzo sprawdza się w większych zbiorach danych. Działa tak, że porównuje sąsiadujące ze sobą elementy i zamienia je miejscami, jeśli są w złej kolejności. Trochę to czasochłonne, ale warto znać ten algorytm, bo pokazuje podstawy sortowania.
Wypisanie elementów tablicy ma złożoność O(n), bo po prostu przechodzimy przez tablicę raz. Wyszukiwanie binarne, z drugiej strony, to coś, co ma złożoność O(log n) i działa w posortowanej tablicy – nie ma tu mowy o sortowaniu. A jeśli chodzi o sortowanie szybkie, to jego złożoność to O(n log n) i jest jednym z najszybszych sposobów sortowania. Więc nie pomylić sortowania z wyszukiwaniem, bo to dwie różne bajki.