Jest to jeden z najprostszych algorytmów sortowania. Sortowanie bąbelkowe jest wykonywane w \( n-1 \) fazach. W fazie \( i \)-tej wyznaczany jest \( i \)-ty najmniejszy element. Załóżmy, że po \( i-1 \) pierwszych fazach mamy wyznaczone i uporządkowane \( i-1 \) najmniejsze elementy, tzn. \( a[1]\le a[2]\le \ldots a[i-1] \) i dla każdego \( k = i, i+1, \ldots, n \) mamy \( a[i-1] \le a[k] \). W fazie \( i \)-tej porównywane są kolejno elementy w parach \( (a[n], a[n-1]) \), \( (a[n-1], a[n-2]) \), ..., \( (a[i+1], a[i]) \). Jeżeli elementy w parze nie są uporządkowane, dokonujemy ich zamiany. Oto algorytm sortowania bąbelkowego.
Algorytm Sortowanie bąbelkowe
BubbleSort
for i:=1 to n-1 do
for j:=n downto i+1 do
if a[j-1] > a[j] then
Exchange(j-1,j);
Zaletą sortowania bąbelkowego jest jego prostota i bardzo krótki kod. Niestety jego główną wadą jest to, że zawsze, niezależnie od danych, wykonuje tyle samo porównań: \( n-1 \) w pierwszej fazie, \( n-2 \) w drugiej, ..., \( 1 \) w fazie ostatniej, co daje łącznie \( \sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2} \) porównań. Liczba zamian może się zmieniać od \( 0 \) do \( \frac{n(n-1)}{2}. \) Zauważmy, że tak zapisany algorytm sortowania bąbelkowego zawsze wykonuje \( n-1 \) faz, nawet wtedy, gdy ciąg wejściowy jest już uporządkowany. Celem ćwiczenia 1 jest taka modyfikacja algorytmu, aby zakończyć jego działanie, kiedy tylko zostanie stwierdzone, że tablica \( a \) jest już uporządkowana.
Ćwiczenie 1
Zmodyfikuj algorytm sortowania bąbelkowego w taki sposób, żeby jego wykonywanie kończyło się z chwilą stwierdzenia, że tablica \( a \) jest już posortowana.