預計在泡沫互換的數目排序

可能重複：
Number of swaps in Bubble Sort 預計在泡沫互換的數目排序

問題是下面簡要說明：
鑑於Ñ整數的數組A中，在每個元件陣列可以增加一個固定的數字b有一些概率 p [ i]，0 < = i < n。我必須找到將使用bubble sort排序陣列的預期交換次數。

我已嘗試以下步驟：

1）的元素A [我]> A [Ĵ用於我 < Ĵ可以很容易地從給定的計算出的概率概率。 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 []將與數字A交換。[j]。

我已經發布了a similar question之前，但它沒有所有的限制。

我沒有得到任何好的提示，無論我是否在正確的軌道上，所以我列出了所有的限制。如果我以不正確的方式思考問題，請給我一些提示。

來源

2012-07-05 TheRock

你也可以進行氣泡排序並計算實際交換次數;）無論如何，你說「數組中的每個元素都可以用某個概率p [i]增加一個固定數值'b'。這是什麼時候發生的？在每個交換？在排序之前？ – SingerOfTheFall

這發生在數組排序之前。我認爲執行冒泡排序會使程序真的很慢，因爲它增加了複雜性，我將不得不爲數組的每個可能的配置運行它。 – TheRock

你真的認爲如果這是一個編程問題？這聽起來像是紙上的問題。如果你正在編寫一個程序並找到這個期望的數字，那麼這有什麼實際用途？ – PermanentGuest

給定元素的預期交換次數是其左側元素的預期數量，它大於它。

您可以通過指標變量的方法以及預期值具有linearity property的事實快速計算此值。

因此，假設您正在考慮元素a_3。然後的時候，它將被交換的預期數量僅僅是

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

右側的每個個體期望都可以使用基本概率輕鬆計算。

然後，預期的掉期總數就是每個元素的期望交換次數除以2後的總和（因爲你加倍計數）。

來源

2012-07-05 08:40:55 tskuzzy

我沒有明確爲什麼它被兩分爲二。你可以多說一點嗎？ – TheRock

如果你有最小的序列[2,1]，那麼你可以計算兩次交換而不減半，因爲你會期望一次交換2和1次交換。但是對於每次交換，都涉及兩個元素。 – Vatine

@Vatine：我爲什麼期望交換2，因爲它沒有任何元素，它比上面的答案中所說的更大，我只能計算一個交換1，因爲它是唯一的元素這可能比左側的值大。 – TheRock

預計在泡沫互換的數目排序

回答

相關問題