在冒泡排序掉期预计数 [英] Expected number of swaps in bubble sort

问题描述

可能重复：
  在泡沫互换数排序

Possible Duplicate:
Number of swaps in Bubble Sort

问题简述如下声明：
鉴于一个数组A的 N 的整数，阵列中的每个元素都可以增加一个固定数量的 B 的一些概率 P [我]，0℃=的我的＆LT; N 的。我必须要找到掉期，将采取地方使用冒泡排序数组排序的预期数量。

The problem is briefly stated below:
Given an array A of N integers, each element in the array can be increased by a fixed number b with some probability p[i], 0 <= i < n. I have to find the expected number of swaps that will take place to sort the array using bubble sort.

我已经试过如下：

1）为元素的概率[我的]> A [Ĵ的]的我的＆LT;的Ĵ的可容易地从给定的概率计算。 2）使用上述的我已经计算互换作为预期数：

1) The probability for an element A[i] > A[j] for i < j can be calculated easily from the given probabilities. 2) Using the above the I have calculated the expected number of swaps as:

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 [Ĵ的。

Basically I came to this idea because the expected number of swaps can be calculated by the number of inversions of the array. So by making use of given probability I am calculating whether a number A[i] will be swapped with a number A[j].

我已经发布之前href="http://stackoverflow.com/questions/11331314/number-of-swaps-in-bubble-sort">过类似的问题，但它没有把所有约束

I have posted a similar question before but it did not had all the constraints.

我没有得到任何好的暗示我是否连在正确的轨道与否，所以我列出的所有约束在这里。请给我一些提示，如果我是一个不正确的思维方式的问题。

I did not get any good hint whether I am even on the right track or not, so I listed all the constraints here. Please give me some hints if I am thinking of the problem in an incorrect way.

推荐答案

掉期给定元素的预期数量是大于它的元素，以它的左边的仅仅是预期数量。

The expected number of swaps for a given element is simply the expected number of elements to the left of it that are greater than it.

您可以通过指针变量的期望值有线性的方法，事实上快速计算这个物业。

You can compute this quickly by the method of indicator variables and the fact that expected values have the linearity property.

因此​​，假设你正在考虑元素 A_3 。然后的时候，它将被交换的期望的数量仅仅是

So suppose you are considering element a_3. Then the expected number of times it will be swapped is simply

E [＃互换A_3的] = E [A_0> A_3] + E [A_1> A3] + E [A_2> A_3]

E[# swaps of a_3] = E[a_0 > a_3] + E[a_1 > a3] + E[a_2 > a_3]

每个的在右手侧的个人期望可以使用基本概率来容易地计算。

Each of the individual expectations on the right hand side can be easily computed using basic probability.

然后互换的预期总数为掉期为除以每个元素的预期数量的简单相加两（因为你重复计算）。

Then the expected total number of swaps is simply the sum of the expected number of swaps for each element divided by two (since you double count).

这篇关于在冒泡排序掉期预计数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！