Aby zaimplementować algorytm sortowania bąbelkowego dla tablicy n-elementowej, potrzeba

Poprawna odpowiedź: D

Uzasadnienie i szersze wyjaśnienie:

Standardowa implementacja sortowania bąbelkowego wymaga użycia dwóch zagnieżdżonych pętli.

• Pętla zewnętrzna odpowiada za kolejne przejścia (pasy) przez tablicę. W najgorszym przypadku musi wykonać się n-1 razy.
• Pętla wewnętrzna odpowiada za porównywanie i ewentualną zamianę sąsiednich elementów w ramach jednego przejścia. Jej zakres również nie przekracza n (a w zoptymalizowanej wersji maleje z każdym przejściem pętli zewnętrznej).

Zatem do implementacji tego algorytmu potrzeba dwóch pętli, z których każda działa na co najwyżej n (lub n-1) elementach.

Dlaczego pozostałe odpowiedzi są nieprawidłowe?

• A: Liczba warunków (porównań) jest rzędu n², a nie n.
• B: Pętle nigdy nie działają na więcej niż n elementach.
• C: Jedna pętla jest niewystarczająca do zaimplementowania tego algorytmu.