在泡掉數排序

我有一個版本的冒泡排序的：在泡掉數排序

int i, j; 

for i from n downto 1 
{ 
    for j from 1 to i-1 
    { 
     if (A[j] > A[j+1]) 
      swap(A[j], A[j+1]) 
    } 
}

我要計算使用冒泡排序以上版本的掉期的預期數量。我使用的方法如下所示：

// 0 based index 

float ans = 0.0; 

for (int i = 0; i < n-1; i++) 
{ 
    for (int j = i+1; j < n; j++) { 

     ans += getprob(a[i], a[j]); // computes probability that a[i]>a[j]. 
    } 
}

我是正確的方式還是我錯過了什麼？

來源

2012-07-04 TheRock

你爲什麼不上隨機數據集運行它，並找出？ –

「有些東西很少是浮動的。我完全不理解'getprob（）'，它會得到數字，所以它可以......完全回答，有什麼概率？ – unwind

這可能比在程序中更容易在紙上解決。 –

獲得答案的最好方法是在swap（）調用之後運行冒泡排序算法本身幷包含一個計數器。你的計算函數（a）需要幾乎與排序本身一樣長（取決於swap（）和getprob（））和（b）的運行時間，因此錯過了排序時元素順序改變的點。

順便說一句，swap（）調用的確切數量取決於您需要排序的數據 - 您有n *（n-1）/ 2次比較，其中任何一次都會導致交換（平均而言，您需要交換比較元素的時間）。

來源

2012-07-04 15:04:07

@C Stoll：我明白你的觀點，平均一半的時間你需要交換比較的元素，但是這有一個假設，每個元素a [i]> a [j]（i a [j]（i TheRock

@TheRock交換次數_is_數組中的反轉次數。如果所有數組條目都不相同，並且置換是均勻分佈的，則交換的期望數量就是「n *（n-1）/ 4」。如果'getprob（）'獨立於值/位置，'p * n *（n-1）/ 2'。但是你似乎有一些更復雜的限制。 –

@DanielFischer：在我的情況下，我不需要爲一般情況做任何事情，每個數組元素都可以隨某些概率而改變，並且我可以得到[i]> a [j]（i TheRock

也許這有助於。基本上，這提供了一個框架來對一組仿真數據集進行冒泡排序並計算交換概率。

讓這個概率= p 然後爲了找到交換操作的預期數量，您需要將其應用於真實數據集。設n是這個數據集的大小。 Then expected number = swapProbability * n * n

n * n是因爲冒泡排序有n * n個預期操作。

float computeSwapProbability() 
{ 
    int aNumSwaps = 0 
    int aTotalNumberOfOperations = 0 

    For all simulation datasets 
    { 


     int i, j; 

     for i from n downto 1 

     { 

      for j from 1 to i-1 

      { 
       aTotalNumberOfOperations++ 

       if (A[j] > A[j+1]) 
       { 
        swap(A[j], A[j+1]) 
        aNumSwaps++ 
       } 

      } 

     } 
    } 

    return (float)aNumSwaps/aTotalNumberOfOperations; 
}

來源

2012-07-04 15:10:31 PermanentGuest

The best way to count swap is to include counter variable inside swap if condition . 

    int swapCount=0; 

    for (i = 0; i < (length-1); ++i) { 
     for (j = 0; j < (length-i-1); ++j) { 
     if(array[j] > array[j+1]) { 
      temp = array[j+1]; 
      array[j+1] = array[j]; 
      array[j] = temp; 
      swapCount++; 
     } 
     } 
    } 

    printf("Swap count : %d" ,swapCount);

來源

2013-08-24 22:41:38

在泡掉數排序

回答

相關問題