Ожидаемое количество свопов в пузырьковой сортировке

14

Учитывая массив из целых чисел, каждый элемент в массиве может быть увеличен на фиксированное число с некоторой вероятностью , . Я должен найти ожидаемое количество перестановок, которые будут иметь место для сортировки массива с помощью пузырьковой сортировки .ANbp[i]0i<n

Я пробовал следующее:

  1. Вероятность для элемента для может быть легко вычислена из заданных вероятностей.A[i]>A[j]i<j

  2. Используя вышесказанное, я рассчитал ожидаемое количество свопов как:

    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.
    

В основном я пришел к этой идее, потому что ожидаемое количество свопов можно рассчитать по количеству инверсий массива. Таким образом, используя данную вероятность, я вычисляю, будет ли число поменяно местами с числом .A [ j ]A[i]A[j]

Обратите внимание, что исходные элементы массива могут быть в любом порядке, отсортированы или не отсортированы. Тогда каждое число может измениться с некоторой вероятностью. После этого мне нужно рассчитать ожидаемое количество свопов.

Я уже писал подобный вопрос, но он не имел всех ограничений.

Я не получил никаких хороших подсказок о том, нахожусь ли я даже на правильном пути или нет, поэтому я перечислил все ограничения здесь. Пожалуйста, дайте мне несколько советов, если я думаю о проблеме неправильно.

Сообщество
источник
6
Симпатичный тпё в названии, правда.
Джефф
Разве вы не имеете в виду, дать отсортированный массив из N целых чисел, каждый элемент ... Кроме того, диапазон чисел в исходном массиве и различий между ними, относительно b, кажется, отсутствует.
Дэнни Варод
Имейте в виду, что для такого рода анализа вы должны очень четко указать, какую именно «реализацию» предложит идея Bubblesort. Было бы лучше, если бы вы дали алгоритм в псевдокоде.
Рафаэль
Эта проблема из продолжающегося конкурса на сайте codechef codechef.com/JULY12/problems/LEBOBBLE. Я буду рад опубликовать свой подход после конкурса.
rizwanhudda

Ответы:

11

Пусть определяется следующим образом: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)

Учитывая некоторую перестановку , говорят , что инверсия произошла, если x j < x ix1,,xnxj<xi для некоторого Мы видим , что B U Ь б л е S O R T выполняет проверку инверсии для каждой пары, и если да, то выполняет своп. Пусть X будет количеством свопов. Нетрудно увидеть, в худшем случае есть X = ( ni<j.BubbleSortX возможны перестановки. Но нас интересует ожидаемый случай, который мы можем вычислить, определивXв терминах инверсий вBubbleSort.X=(n2)XBubbleSort

Пусть теперь где I i j - переменная индикатора, для которой существует инверсия для некоторой пары ( i , j ) . Ожидание определяется как E [ X ]X=ji<jIijIij(i,j)E[X]=E[ji<jIij]=ji<jE[Iij], Теперь нам нужно определить .P{Iij}

Принимая любую возможную перестановку в качестве входных данных, каждая с одинаковой вероятностью, можно показать, что . Причина этого заключается в том, что при любой возможной перестановке половина времениxj<xiи половина времениxi<xjдляij.P{Iij}=12xj<xixi<xjij

E[X]=ji<jE[Iij]=ji<j12=(n2)12=n(n1)4

Николас Манкузо
источник