Pytanie 1
Który z podanych algorytmów operujących na jednowymiarowej tablicy posiada złożoność obliczeniową O(n2)?
A. Wyszukiwanie binarne
B. Sortowanie bąbelkowe
C. Wypisanie elementów
D. Sortowanie szybkie
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).
