Erwartete Anzahl von Swaps in der Blasensortierung

Bei einem Array von ganzen Zahlen kann jedes Element in dem Array mit einer gewissen Wahrscheinlichkeit , um eine feste Zahl erhöht werden . Ich muss die erwartete Anzahl von Swaps finden, die stattfinden werden, um das Array mithilfe der Blasensortierung zu sortieren .N b p [ i ] 0 ≤ i < $A$$N$$b$$p[i]$$0 \leq i < n$

Ich habe Folgendes versucht:

1. Die Wahrscheinlichkeit für ein Element für kann leicht aus den gegebenen Wahrscheinlichkeiten berechnet werden.i < $A[i] > A[j]$$i < j$

2. Mit den obigen Angaben habe ich die erwartete Anzahl von Swaps wie folgt berechnet:

   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.
   

Grundsätzlich bin ich auf diese Idee gekommen, weil sich die erwartete Anzahl von Swaps aus der Anzahl der Inversionen des Arrays berechnen lässt. Also berechne ich unter Verwendung der gegebenen Wahrscheinlichkeit, ob eine Zahl mit einer Zahl getauscht wird .A [ j $A[i]$$A[j]$

Beachten Sie, dass die anfänglichen Array-Elemente in beliebiger Reihenfolge sortiert oder unsortiert sein können. Dann kann sich jede Zahl mit einiger Wahrscheinlichkeit ändern. Danach muss ich die erwartete Anzahl von Swaps berechnen.

Ich habe zuvor eine ähnliche Frage gestellt, aber sie enthielt nicht alle Einschränkungen.

Ich habe keine guten Tipps bekommen, ob ich überhaupt auf dem richtigen Weg bin oder nicht, deshalb habe ich hier alle Einschränkungen aufgelistet. Bitte geben Sie mir einige Hinweise, wenn ich falsch über das Problem nachdenke.

Lassen wie folgt definiert werden:$\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)

Bei einer gewissen Permutation soll eine Inversion aufgetreten sein, wenn x j < x i für einige i < j ist . Wir sehen , dass B u B b l e S o r t führt eine Invertierung Prüfung für jedes Paar, und falls dem so ist , führt einen Swap. Sei X die Anzahl der Swaps. Es ist nicht schwer zu sehen, im schlimmsten Fall gibt es X = ($x_1, \cdots, x_n$$x_j < x_i$$i < j.$$\sf{Bubble Sort}$$X$ mögliche getauschte Swaps. Wir interessieren uns jedoch für den erwarteten Fall, den wir berechnen können, indem wirXin Form von Inversionen inBubbleSort definieren.$X = \binom{n}{2}$$X$$\sf{Bubble Sort}$

Nun wollen wir wo ich i j ist die Indikatorvariable , dass es für einige Paar eine Umkehrung existiert ( i , j ) . Die Erwartung ist definiert als 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}]$. Wir müssen nun bestimmen .$P\{I_{ij}\}$

Unter der Annahme einer möglichen Permutation als Eingabe mit jeweils einheitlicher Wahrscheinlichkeit kann gezeigt werden, dass . Der Grund dafür ist, dass bei jeder möglichen Permutation die Hälfte der Zeitxj<xiund die Hälfte der Zeitxi<xjfüri≠j gilt.$P\{I_{ij}\} = \frac{1}{2}$$x_j < x_i$$x_i < x_j$$i \neq j$

Kehren wir zu unserem Erwartungs Berechnung sehen wir , dass $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}$