Oczekiwana liczba zamian w sortowaniu bąbelkowym

Biorąc pod uwagę tablicy z liczb całkowitych, do każdego elementu w szyku może być zwiększona przez ustaloną ilość z pewnym prawdopodobieństwem , . 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:

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

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[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.

— Społeczność
źródło

W tytule jest jednak słodkie tpyo.

— JeffE

Nie masz na myśli, podaj posortowaną tablicę N liczb całkowitych, każdego elementu ... Wydaje się, że brakuje także zakresu liczb w tablicy początkowej i różnic między nimi w stosunku do b.

— Danny Varod,

Należy pamiętać, że w przypadku tego rodzaju analiz należy bardzo wyraźnie określić, jaką konkretną „implementację” należy wziąć pod uwagę w przypadku idei Bubblesort. Byłoby najlepiej, gdybyś podał algorytm w pseudo-kodzie.

— Raphael

Ten problem pochodzi z trwającego konkursu na stronie codechef codechef.com/JULY12/problems/LEBOBBLE Z przyjemnością opublikuję moje podejście po konkursie.

— rizwanhudda

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 dla niektórych Możemy zobaczyć, że wykonuje sprawdzenie inwersji dla każdej pary, a jeżeli tak, wykonuje wymiany. Niech będzie liczbą zamian. Nie jest trudno dostrzec w najgorszym przypadku $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ącw kategoriach inwersji w $X = \binom{n}{2}$ $X$ . $\sf{Bubble Sort}$

Teraz niech gdzie jest zmienną wskaźnikową, że istnieje odwrócenie dla pewnej pary . Oczekiwanie jest zdefiniowane jako $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 czasupołowa czasudla. $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}$

— Nicholas Mancuso
źródło