ID: 2733
Algorytmy
Łatwe
Źródło: Arkusze CKE
W którym przypadku algorytm sortowania bąbelkowego działa z optymalną wydajnością?
Warianty odpowiedzi
-
A
Dla tablicy z dużą liczbą powtórzeń
-
B
Dla tablicy uporządkowanej rosnąco
-
C
Dla tablicy uporządkowanej malejąco
-
D
Dla tablicy losowej
Wyjaśnienie
Wyobraź sobie, że przeglądasz elementy w tablicy po kolei i sprawdzasz, czy są w dobrej kolejności.
W zoptymalizowanej wersji sortowania bąbelkowego algorytm używa specjalnej flagi. Śledzi ona, czy podczas przejścia przez tablicę doszło do jakiejkolwiek zamiany elementów.
Jeśli dostaniemy tablicę, która jest już idealnie posortowana rosnąco, algorytm przejdzie przez nią tylko raz. Zauważy, że nic nie musiał zamieniać i natychmiast zakończy pracę.
Dzięki temu złożoność spada z pesymistycznego O(n^2) do liniowego O(n). To najlepszy możliwy scenariusz dla tego algorytmu.