Ile porównań muszą wykonać dwa rodzaje sortowania?

Question

Witam,

Ile porównań musi wykonać każdy z algorytmów sortowania(bąbelkowanie i przez wstawianie) dla 4 elementowego ciągu odwróconego (np. 10,5,3,1) i już posortowanego (np. 1, 3, 5, 10)?

Answer 1

Poczytaj sobie o tych algorytmach w jaki sposob dzialaja i sprobuj sobie na kartce rozrysowac kazdy przebieg sortowania. Ogolnie jezeli chodzi o sortowanie babelkowe, to przy takim ukladzie zlozonosc wynosi O(n^2), A jezeli chodzi o sortowanie przez wstawianie to w takim ulozeniu chyba wynosi O(n).

Comments

Wszystko tak naprawdę zależy od tego w jaki sposób sortujesz. Polecam poczytać Cormena - Wprowadzenie do algorytmów.