W pytaniu opisano sortowanie polegające na wielokrotnym wykonywaniu przebiegów po tablicy, podczas których porównuje się dwa sąsiadujące elementy (np. a[i] i a[i+1]) i w razie potrzeby zamienia miejscami. To klasyczna definicja sortowania bąbelkowego (bubble sort).
Dlaczego "bąbelkowe" jest poprawne?
Po jednym pełnym przebiegu największy element (dla sortowania rosnącego) "przesuwa się" na koniec tablicy, ponieważ jest wielokrotnie porównywany z następnym sąsiadem i w razie potrzeby przesuwany w prawo. Po kolejnym przebiegu na swoje miejsce trafia następny największy element itd. Ten efekt stopniowego "wypływania" wartości jest charakterystyczny i odróżnia bubble sort od innych metod.
Dlaczego pozostałe odpowiedzi są niepoprawne?
- Sortowanie przez wybór – w każdym kroku wybiera się element minimalny/maksymalny z nieuporządkowanej części i umieszcza na właściwej pozycji. Kluczowe jest wyszukiwanie ekstremum w całym fragmencie, a nie porównywanie wyłącznie sąsiadów.
- Sortowanie szybkie – opiera się na podziale względem elementu rozdzielającego (pivot) i rekurencyjnym sortowaniu podtablic. Nie jest definiowane jako n-krotne porównywanie sąsiadów w kolejnych przebiegach.
- Sortowanie przez scalanie – dzieli dane na części, sortuje je (rekurencyjnie) i następnie scala w jeden uporządkowany ciąg. Sednem jest etap scalania dwóch uporządkowanych sekwencji, a nie lokalne zamiany sąsiadów.
Wskazówka egzaminacyjna: jeśli w opisie pojawia się "porównywanie sąsiadów + zamiana miejscami + kolejne przebiegi", to niemal zawsze chodzi o sortowanie bąbelkowe. Gdy jest "szukanie minimum/maksimum" – to zwykle wybór; gdy "pivot/podział" – szybkie; gdy "dziel i scalaj/merge" – scalanie.
