Sortowanie bąbelkowe

Na czym polega sortowanie bąbelkowe?

Wikipedia: “[Sortowanie bąbelkowe] Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.”

Wizualizacja

Pseudokod

procedure bubbleSort( A : lista elementów do posortowania )
  n = liczba_elementów(A)
   do
    for (i = 0; i < n-1; i++) do:
      if A[i] > A[i+1] then
        swap(A[i], A[i+1])
      end if
    end for
    n = n-1 # Dlaczego?
  while n > 1
end procedure

Co należy zaimplementować?

1. Zaimplementuj funkcję bubble_sort(), która jako argument przyjmuje listę a zwraca listę posortowaną.
2. W funkcji main() wygeneruj losową listę liczb o długości N=1000.
3. Posortuj tę listę wykorzystując bubble_sort().
4. Sprawdź czy lista zwrócona przez funkcję jest posortowana.
5. Zmierz czas potrzebny na wykonanie sortowania N = {10, 100, 1000, 10000} liczb.

Pytania

1. Jak rośnie czas wykonania algorymtu wraz ze wzrostem długości danych N (liniowo, kwadratowo, logarytmicznie, …)?
2. Ile maksymalnie porównań może wykonać zaimplementowane sortowanie (w funkcji N)?
3. Czy masz jakieś pomysły na usprawnienie sortowania bąbelkowego?