Lekcja: "Algorytmy sortujące - sortowanie bąbelkowe, część II"
Optymalizacja algorytmu
Algorytm sortowania bąbelkowego wykonuje dwa rodzaje operacji:
test bez zamiany miejsc elementów – operacja ta nie sortuje zbioru, jest więc operacją pustą
test ze zamianą miejsc elementów - operacja dokonuje faktycznej zmiany porządku elementów, jest zatem operacją sortującą
Ze względu na przyjęty sposób sortowania algorytm bąbelkowy zawsze musi wykonać tyle samo operacji sortujących. Tego nie możemy zmienić. Jednakże możemy wpłynąć na eliminację operacji pustych. W ten sposób usprawnimy działanie algorytmu.
Po dokładnym przeanalizowaniu przykładu 1 i 2 z pierwszej części lekcji "Algorytmy bąbelkowe", można dokonać następujących spostrzeżeń:
przykład 1 jest najmniej optymalną wersją algorytmu bąbelkowego. Wykonywane są wszystkie możliwe operacje sortujące i puste
przykład 2 redukuje ilość operacji pustych poprzez ograniczanie liczby obiegów pętli wewnętrznej (sortującej)