El conocido Bubblesort algoritmo ordena una lista $a_1, a_2, . . . , a_n$ de los números por en repetidas ocasiones el intercambio de números adyacentes que están invertidos (es decir, en la equivocada relación de orden) hasta que no quede ningún resto de inversiones. (Tenga en cuenta que el número de intercambios requerido no dependen del orden en el que los intercambios se hacen.) Suponga que la entrada Bubblesort es un permutación aleatoria de los números de $a_1, a_2, . . . , a_n$ , de modo que todos los $n!$ órdenes son igualmente probables, y que todos los números son distintos. Lo que se espera que el número de intercambios realizados por Bubblesort?
Respuesta
¿Demasiados anuncios?
SUMIT MITRA
Puntos
16
Debe ser igual que el número esperado de las inversiones en una permutación aleatoria. Recordemos que una inversión es un par $(i,j)$$\pi(i)>\pi(j)$. No es difícil mostrar que si una permutación ha $N$ inversiones, que es la longitud de la Burbuja de la clasificación. Para ver esto, mostrar que la identidad de permutación es la única permutación con 0 inversiones y que la realización de un paso de la burbuja para ordenar la baja de la inversión número de exactamente 1.
Calcular el número esperado de las inversiones: Para una permutación de longitud $n$, vamos a $I_{ij}=1$ si $(i,j)$ es una inversión. A continuación,$\mathbb{E}[I_{i,j}]=P((i,j)\mbox{ is an inversion})=1/2$. Esto es fácil ver por simetría: para cualquier par de $(i,j)$ que es una inversión, $(j,i)$ no es una inversión.
A continuación, el número esperado de las inversiones es:
$$\mathbb{E}[\sum_{i=1}^n\sum_{j>i}^n I_{ij}]=\sum_{i=1}^n\sum_{j>i}^n \frac{1}{2}=\binom{n}{2}\frac{1}{2}=\frac{n(n-1)}{4}$$.
También se puede calcular de otra manera. Cada permutación $\pi$ $N$ inversiones se pueden leer al revés para dar una permutación con $\binom{n}{2}-N$ de las inversiones. Esto le da un 1-1 mapa entre permutaciones con $N$ inversiones y $\binom{n}{2}-N$ de las inversiones. A continuación, por la simetría es claro que el valor esperado es $\frac{1}{2}\binom{n}{2}$.
