Babelkowe sortowanie - analiza

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

1. Jak policzyć dokładną złożoność? Policzyć po prostu. Masz tutaj sumę szeregu:
   n+(n-1)+...+1
2. Poczatkowo ilość el w części posortowanej wynosi 0. Wykaż że w każdym przejściu pętli wewnętrznej rozmiar części posortowanej zwiększa się o 1 (o co najmniej 1).

ok, dzieki
mam tylko pytanie odnosnie tego szeregu, za bardzo tego nie widze xD

ja liczylem tak (ci odnosi sie do i-tej linijki)

c1 - n-1
c2 - n(n-1)
c3 - nie mam pomyslu
c4 - nie mam pomyslu

W pierwszym obiegu pętli zewnętrznej pętla wewnętrzna przelatuje n razy.
W kolejnym n-1 razy
...
w ostatnim 1 raz

Wiec jeśli koszt jednego obrotu pętli wewnętrznej to C to koszt całego algorytmu to:
c* (n+(n-1)+(n-2)+...+1)
a to zwykły ciag arytmetyczny o pierwszym wyrazie = 1, r = 1 i ilości wyrazów n.

ok, dzieki, wszystko jasne

mam tylko dwa pytanka:
1)czy w pierwszym obiegu pętli zewnętrznej pętla wewnętrzna nie przelatuje przypadkiem n-1 razy

2. czy koszty wierszy 3 i 4 mozemy tak sobie pominac?

Moze n-1 razy, nie jest to aż takie ważne ;]
Kosz liczysz tylko dla operacji dominujacych, czyli porównania i podstawienia w tym przypadku.

        procedure SORT_BY_DATE(var p : kupa);
      var
      i:integer; j:integer; tmp:tblock;
      begin

       for i := length(p)-2 downto 0 do

            for j := 0 to i do      begin


               if p[j].dataurodzenia > p[j + 1].dataurodzenia then begin

                    tmp := EQUALIZE_RECORD(p[j]);

               p[j] := EQUALIZE_RECORD(p[j + 1]);

               p[j + 1] := EQUALIZE_RECORD(tmp);

                end;


            end;

           end;