algorytm sortowania głupiego (naiwnego) - stupid bubble sort

Jak obliczyć złożoność czasową algorytmu. Wiem, że jest to złożoność sześcienna. Jednak w jaki sposób wyprowadzić wzór na nią (by program mógł dla porównania różnych rozmiarów tablicy go obliczać)?
Będę bardzo wdzięczny za pomoc

 static int StupidBubbleSort(int T[ ], int n){
        int Element;
        int Licznik = 0;
        int i;
        if(n>0)
        {
            i=0;
            do
            {
                    if(T[i]>T[i+1]){ // porównywanie kolejnych par sąsiednich elementów sortowanego zbioru i zamiana ich miejscami
                    Licznik++; 
                    Element=T[i];
                    T[i]=T[i+1];
                    T[i+1]=Element;
                    i=0; //rozpoczęcie całej operacji porównywania od początku zbioru
                    Licznik++;
                    continue;
                }
                i++;                
            } while(i<n-1);
            return Licznik;
        }
        return Licznik;
    }
          

podstawowy bubble sort jest Θ(n^2). Chcesz na podstawie wielkosci danych wejsciowych wyliczyc czas potrzebny do posortowania ?

http://edu.i-lo.tarnow.pl/inf/alg/003_sort/0003.php => O(n3) ???

tak. np. rozmiar tablicy 5 elementow - ... analityczny koszt czasowy
25 elemtow - ... analityczny koszt czasowy

Ten algorytm ma złożoność O(n^3). Najgorszy przypadek to tablica posortowana odwrotnie. Co do oczka na razie nie chce mi się liczyć operacji.

sortowanie rosnąco zbioru z losowym rozkładem elementów

donkey7 napisał(a)

Ten algorytm ma złożoność O(n^3). Najgorszy przypadek to tablica posortowana odwrotnie. Co do oczka na razie nie chce mi się liczyć operacji.

byłbym wdzięczny mimo wszystko za policzenie:) chciałbym się rozeznać od czego to zależy i jak postąpić w przypadku innych algorytmów.

przypuśćmy, że obliczam to dla t[i]. więc jak obliczyć wzór na koszt czasowy dla i-elementowej tablicy w/g tego algorytmu sortowania? proszę chociaż o podpowiedź.

proszę mnie poprawić, jeśli się mylę. czy koszt czasowy jest w tym przypadku równy operacjom dominującym (jak np. w SelectionSort ) czy się od nich różni?

To mój wynik:

Rozmiar tablicy: 5 => Wykonane operacje dominujące: 2 => Analityczny koszt czasowy: 30
Rozmiar tablicy: 25 => Wykonane operacje dominujące: 140 => Analityczny koszt czasowy: 900

poprawnie, że koszt czasowy = 3*(i*i-i)/2;?

Jeśli T(n) to pesymistyczna ilość porównań dla wejścia rozmiaru n to:
T(1) = 0
T(n + 1) = T(n) + (sum j, j = 1..n)

Rozwiązanie:
<a href=http://www.wolframalpha.com/input/?i=T(n+%2B+1)+%3D+T(n)+%2B+(sum+j,+j+%3D+1..n),+T(1)+%3D+0>WolframAlpha</a>

proszę o ten wzór albo wytłumaczenie...

Dziękuję uprzejmie i przepraszam za kłopot. Serdecznie pozdrawiam:)

Spoko, ale nie daję gwarancji na to :)

Czy analityczny koszt czasowy jest równy liczbie operacji dominujących?

donkey7 napisał(a)

Spoko, ale nie daję gwarancji na to :)

jeśli operacje dominujące to porównanie i zamiana miejscami, to w/g wstawionego licznika do algorytmu - wyniki się zgadzają:)
tak więc czy powinny być równe ilości O.D.?

W zasadzie to chciałem liczyć same porównania, bo ilość zamian miejscami jest zwykle sporo mniejsza.

Dla tego algorytmu:

 static int StupidBubbleSort(int T[ ], int n){
        int Element;
        int Licznik = 0;
        int i;
        if(n>0)
        {
            i=0;
            do
            {       Licznik++;
                    if(T[i]>T[i+1]){ // porównywanie kolejnych par sąsiednich elementów sortowanego zbioru (operacja dominująca)
                    Element=T[i];
                    T[i]=T[i+1]; // zamiana ich miejscami (operacja dominująca)
                    T[i+1]=Element;
                    Licznik++;
                    i=0; //rozpoczęcie całej operacji porównywania od początku zbioru
                    continue;
                    }
                    
                i++;                
            } while(i<n-1);
        }
        return Licznik;
    }

wyniki wzoru: http://www3.wolframalpha.com/Calculate/MSP/MSP1721119d3aag5e2fh92da0000322c81i2ba300b8e?MSPStoreType=image/gif&s=33&w=208&h=72 są identyczne (czyli porównania+zamiany miejscami). Moje pytanie jeszcze brzmi, czy ilość operacji dominujących będzie równa złożoności czasowej?

z tego co wiem to notacja 'duzego O' jest ograniczeniem od gory, czyli przypadek pesymistyczny, jesli ten algorytm dostanie posortowane dane(co podpada pod losowy rozklad elementow) to bedzie mial zlozonosc Ω(n), Ω oznacza ograniczenie od dolu. Dlatego tez nie mozesz wyliczyc dokladnie ilosci operacji na podstawie tylko rozmiaru danych wejsciowych. dlatego wczesniej pisalem o standardowym sortowaniu bablekowym ktore zawsze robi tyle samo operacji porownania.
Cormen -> rozdzial 2 -> rysunek 2.1
Nie mam za to pojecia jak sie usrednia ilosc operacji :)

Operacją dominującą są tutaj porównania i wyliczyłem ich pesymistyczną ilość.

Średnią ilość operacji dla wejścia o danym rozmiarze liczy się np poprzez policzenie średniej ważonej (chociaż zwykle wagi są równe) ze złożoności dla każdej permutacji danych wejściowych.