Nombre prévu de swaps en tri à bulles

14

Étant donné un tableau de entiers, chaque élément du tableau peut être augmenté d'un nombre fixe avec une certaine probabilité , 0 \ leq i <n . Je dois trouver le nombre attendu de swaps qui auront lieu pour trier le tableau à l'aide du tri à bulles .ANbp[i]0i<n

J'ai essayé ce qui suit:

  1. La probabilité pour un élément A[i]>A[j] pour i<j peut être calculée facilement à partir des probabilités données.

  2. En utilisant ce qui précède, j'ai calculé le nombre attendu de swaps comme suit:

    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.
    

Fondamentalement, je suis venu à cette idée parce que le nombre attendu de swaps peut être calculé par le nombre d'inversions du tableau. Donc, en utilisant une probabilité donnée, je calcule si un nombre A[i] sera échangé avec un nombre A[j] .

Notez que les éléments du tableau initial peuvent être dans n'importe quel ordre, triés ou non triés. Ensuite, chaque nombre peut changer avec une certaine probabilité. Après cela, je dois calculer le nombre attendu de swaps.

J'ai déjà posé une question similaire mais elle n'avait pas toutes les contraintes.

Je n'ai pas obtenu de bons indices pour savoir si je suis même sur la bonne voie ou non, j'ai donc énuméré toutes les contraintes ici. Veuillez me donner quelques conseils si je pense au problème de manière incorrecte.

Communauté
la source
6
Tpyo mignon dans le titre, cependant.
JeffE
Ne voulez-vous pas dire, donnez un tableau trié de N entiers, chaque élément ... De plus, la plage des nombres dans le tableau initial et les différences entre eux, par rapport à b semblent manquer.
Danny Varod
Gardez à l'esprit que pour ce type d'analyse, vous devez indiquer très clairement quelle "implémentation" particulière si vous pensez à l'idée de Bubblesort. Il serait préférable que vous donniez l'algorithme en pseudo-code.
Raphael
Ce problème provient d'un concours en cours sur le site codechef codechef.com/JULY12/problems/LEBOBBLE Je serai heureux de publier mon approche après le concours.
rizwanhudda

Réponses:

11

Soit être défini comme suit:BubbleSort

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)

Étant donné une certaine permutation , une inversion se serait produite si x j < x i pour certains i < j . Nous voyons que B u b b l e S o r t effectue un contrôle d'inversion pour chaque paire, et si c'est le cas, effectue un swap. Soit X le nombre de swaps. Il n'est pas difficile de voir que dans le pire des cas il y a X = ( nx1,,xnxj<xii<j.BubbleSortX échanges possibles. Mais nous nous intéressons au cas attendu, que nous pouvons calculer en définissantXen termes d'inversions dansBubbleSort.X=(n2)XBubbleSort

Soit maintenant I i j est la variable indicatrice qu'il existe une inversion pour une paire ( i , j ) . L'espérance est définie comme E [ X ] = E [ j i < j I i j ] = j i < j E [ I i j ]X=ji<jIijIij(i,j)E[X]=E[ji<jIij]=ji<jE[Iij]. Nous devons maintenant déterminer .P{Iij}

En supposant une permutation possible en entrée, chacune avec une probabilité uniforme, on peut montrer que . Le raisonnement derrière cela est que sous toute permutation possible, la moitié du tempsxj<xiet la moitié du tempsxi<xjpourij.P{Iij}=12xj<xixi<xjij

Revenant à notre calcul des attentes, nous voyons que E[X]=ji<jE[Iij]=ji<j12=(n2)12=n(n1)4

Nicholas Mancuso
la source