BABEL(A)
for i <- 1 to length[A]-1
do for j<-length[A] downto i+1
do if A[j-1] > A[j]
then A[j-1] <-> A[j]
mamy zalozmy taka implementacje tego sortowania. Jak dobrze przeprowadzic analize czasowej zlozonosci obliczeniowej.
Jak korzystajac z niezmiennika petli udowodnic poprawnosc algorytmu.
zlozonosc bedzie pewnie n^2, ale jak to po kolej wykazac?
niezmiennik - przypuszczam ze elementy na lewo od i sa posortwane, ale jezeli ten niezmiennik jest poprawny to jak to wykazac krok po kroku?
z gory dzieki