Pytanie 1
Który z podanych algorytmów operujących na jednowymiarowej tablicy posiada złożoność obliczeniową O(n<sup>2</sup>)?
A. Sortowanie bąbelkowe
B. Sortowanie szybkie
C. Wyszukiwanie binarne
D. Wypisanie elementów
Sortowanie bąbelkowe, znane również jako bubble sort, to prosty algorytm sortowania, który działa na zasadzie wielokrotnego przechodzenia przez tablicę i porównywania sąsiadujących ze sobą elementów. Algorytm ten ma złożoność obliczeniową O(n^2), co oznacza, że w najgorszym przypadku liczba operacji porównania wzrasta kwadratowo wraz ze wzrostem liczby elementów w tablicy. Przykładowo, dla tablicy o 5 elementach algorytm może wykonać do 10 porównań. W praktyce sortowanie bąbelkowe jest rzadko stosowane w dużych zbiorach danych ze względu na swoją niską efektywność, jednak jest to dobry przykład do nauki podstaw algorytmów sortujących. Standardy algorytmów sortujących, takie jak te zawarte w podręcznikach algorytmiki, często używają sortowania bąbelkowego jako przykładu do omówienia prostych koncepcji związanych z sortowaniem. Warto zauważyć, że chociaż algorytm ten jest prosty do zrozumienia, jego złożoność czasowa sprawia, że nie jest on praktyczny do stosowania w produkcyjnych rozwiązaniach, gdyż bardziej optymalne algorytmy, jak sortowanie szybkie czy sortowanie przez scalanie, osiągają złożoność O(n log n).
