Lekcja: "Algorytmy sortujące - sortowanie bąbelkowe, część II"
Optymalizacja algorytmu
Możliwa jest dalsza redukcja operacji pustych, jeśli sprawdzimy, czy w pętli wewnętrznej były przestawiane elementy (czyli czy wykonano operacje sortujące). Jeśli nie, to zbiór jest już posortowany i możemy zakończyć pracę algorytmu.
Teraz rośnie trudność wyznaczenia czasowej złożoności obliczeniowej, ponieważ ilość faktycznie wykonywanych operacji porównań i przestawień zależy od rozkładu elementów w sortowanym zbiorze. Zadanie komplikuje dodatkowo fakt, iż operacja pusta jest zwykle wykonywana kilkakrotnie szybciej od operacji sortującej.
Dla zbioru posortowanego algorytm wykona tylko n-1 operacji pustych, zatem w przypadku najbardziej optymistycznym czasowa złożoność obliczeniowa redukuje się do klasy O(n) - liniowej.
W przypadku najbardziej niekorzystnym algorytm wykona wszystkie operacje puste i sortujące, zatem będzie posiadał klasę czasowej złożoności obliczeniowej O(n2).
