Przykład 14: sortowanie metodą bąbelkową
Program demonstruje sortowanie tablicy liczb metodą bąbelkową.
- Sprawdź działanie programu, podaj szacunkową złożoność algorytmu.
- Uzupełnij program o liczniki, podające dokładne liczby operacji porównania i zamiany.
- Dla jakiego zestawu danych wejściowych wykonywana jest największa liczba operacji (tzw. przypadek pesymistyczny)?
- Czy można zoptymalizować liczbę wykonań pętli wewnętrznej? W jaki sposób?
- 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ć?
- 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.