Erwartete Anzahl von Swaps in der Blasensortierung

14

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 < nEINNbp[ich]0ich<n

Ich habe Folgendes versucht:

  1. Die Wahrscheinlichkeit für ein Element für kann leicht aus den gegebenen Wahrscheinlichkeiten berechnet werden.i < jEIN[ich]>EIN[j]ich<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 ]EIN[ich]EIN[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.

Gemeinschaft
quelle
6
Netter TPYO im Titel, obwohl.
JeffE
Meinen Sie nicht, geben Sie ein sortiertes Array von N ganzen Zahlen an, jedes Element ... Auch der Bereich der Zahlen im anfänglichen Array und die Unterschiede zwischen ihnen, relativ zu b, scheinen zu fehlen.
Danny Varod
Denken Sie daran, dass Sie für diese Art der Analyse sehr deutlich machen müssen, welche bestimmte "Implementierung" Sie bei der Bubblesort-Idee in Betracht ziehen. Am besten geben Sie den Algorithmus in Pseudocode an.
Raphael
Dieses Problem stammt aus einem laufenden Wettbewerb auf der Codechef-Website codechef.com/JULY12/problems/LEBOBBLE. Ich werde meinen Ansatz gerne nach dem Wettbewerb veröffentlichen.
Rizwanhudda

Antworten:

11

Lassen wie folgt definiert werden:BubbleSÖrt

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 = ( nx1,,xnxj<xichich<j.BubbleSÖrtX 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=(n2)XBubbleSÖrt

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=jich<jichichjichichj(ich,j)E[X]=E[jich<jichichj]=jich<jE[ichichj]. Wir müssen nun bestimmen .P{ichichj}

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ürij gilt.P{ichichj}=12xj<xichxich<xjichj

Kehren wir zu unserem Erwartungs Berechnung sehen wir , dass E[X]=jich<jE[ichichj]=jich<j12=(n2)12=n(n-1)4

Nicholas Mancuso
quelle