Oczekiwana liczba zamian w sortowaniu bąbelkowym

Biorąc pod uwagę tablicy z N liczb całkowitych, do każdego elementu w szyku może być zwiększona przez ustaloną ilość b z pewnym prawdopodobieństwem p [ i ] , 0 ≤ i < n . Muszę znaleźć oczekiwaną liczbę zamian, które będą miały miejsce w celu posortowania tablicy za pomocą sortowania bąbelkowego .$A$$N$$b$$p[i]$$0 \leq i < n$

Próbowałem następujące:

1. Prawdopodobieństwo dla elementu dla i < j można łatwo obliczyć na podstawie podanych prawdopodobieństw.$A[i] > A[j]$$i < j$

2. Korzystając z powyższego, obliczyłem oczekiwaną liczbę swapów jako:

   double ans = 0.0;
   for ( int i = 0; i < N-1; i++ ){
       for ( int j = i+1; j < N; j++ ) {
           ans += get_prob(A[i], A[j]); // Computes the probability of A[i]>A[j] for i < j.
   

Zasadniczo wpadłem na ten pomysł, ponieważ oczekiwaną liczbę zamian można obliczyć na podstawie liczby inwersji tablicy. Korzystając z podanego prawdopodobieństwa, obliczam, czy liczba zostanie zamieniona liczbą A [ j ] .$A[i]$$A[j]$

Zauważ, że początkowe elementy tablicy mogą być w dowolnej kolejności, posortowane lub nieposortowane. Następnie każda liczba może się zmienić z pewnym prawdopodobieństwem. Następnie muszę obliczyć oczekiwaną liczbę zamian.

Zadałem podobne pytanie wcześniej, ale nie miało ono wszystkich ograniczeń.

Nie dostałem żadnych dobrych wskazówek, czy jestem na dobrej drodze, czy nie, więc wymieniłem tutaj wszystkie ograniczenia. Proszę o wskazówki, jeśli źle myślę o problemie.

Niech jest zdefiniowana jako:$\sf{Bubble Sort}$

for (j = A.length; j > 1; j--)
    for (i = 0; i < j - 1; i++)
        if (A[i] > A[i + 1])
            swap(i, i + 1, A)

Biorąc pod uwagę pewną permutację , mówi się, że doszło do inwersji, jeśli x j < x i dla niektórych i < j . Możemy zobaczyć, że B u b b L E S O r t wykonuje sprawdzenie inwersji dla każdej pary, a jeżeli tak, wykonuje wymiany. Niech X będzie liczbą zamian. Nie jest trudno dostrzec w najgorszym przypadku X = ($x_1, \cdots, x_n$$x_j < x_i$$i < j.$$\sf{Bubble Sort}$$X$ dokonane możliwe zamiany. Ale interesuje nas oczekiwany przypadek, który możemy obliczyć, definiującXw kategoriach inwersji wBub$X = \binom{n}{2}$$X$ .$\sf{Bubble Sort}$

Teraz niech gdzie I i j jest zmienną wskaźnikową, że istnieje odwrócenie dla pewnej pary ( i , j ) . Oczekiwanie jest zdefiniowane jako E [ X ] = E [ ∑ j ∑ i < j I i j ] = ∑ j ∑ i < j E [ I i j$X = \sum_j \sum_{i<j} I_{ij}$$I_{ij}$$(i,j)$$E[X] = E[\sum_j \sum_{i<j} I_{ij}] = \sum_j \sum_{i<j} E[I_{ij}]$ . Teraz musimy ustalić .$P\{I_{ij}\}$

Zakładając jakąkolwiek możliwą permutację jako dane wejściowe, każde z jednakowym prawdopodobieństwem, można wykazać, że . Powodem tego jest to, że przy dowolnej możliwej permutacji połowa czasuxj<xiipołowa czasuxi<xjdlai≠j.$P\{I_{ij}\} = \frac{1}{2}$$x_j < x_i$$x_i < x_j$$i \neq j$

$E[X] = \sum_j \sum_{i<j}E[I_{ij}] = \sum_j \sum_{i<j} \frac{1}{2} = \binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}$