Przykład 14: sortowanie metodą bąbelkową

Program demonstruje sortowanie tablicy liczb metodą bąbelkową.

  1. Sprawdź działanie programu, podaj szacunkową złożoność algorytmu.
  2. Uzupełnij program o liczniki, podające dokładne liczby operacji porównania i zamiany.
  3. Dla jakiego zestawu danych wejściowych wykonywana jest największa liczba operacji (tzw. przypadek pesymistyczny)?
  4. Czy można zoptymalizować liczbę wykonań pętli wewnętrznej? W jaki sposób?
  5. Uzupełnij program o sprawdzanie, czy zostały wykonane jakieś zamiany w danym przebiegu pętli. Co oznacza brak zamian? Jak można to wykorzystać?
  6. Porównaj liczbę operacji porównania i zamiany dla wersji początkowej algorytmu i po poprawkach. Porównanie wykonaj dla różnych zestawów danych: losowego, pesymistycznego i optymistycznego.