title: Expected number of swaps in bubble sort
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/11331314/number-of-swaps-in-bubble-sort">Number of swaps in Bubble Sort</a>  </p>
  </blockquote>
  
  
  
  <p>The problem is briefly stated below:<br>
  Given an array A of <em>N</em> integers, each element in the array can be increased by a fixed number <em>b</em> with some probability <i>p</i>[<i>i</i>], 0 &lt;= <em>i</em> &lt; <em>n</em>. I have to find the expected number of swaps that will take place to sort the array using <a href="http://en.wikipedia.org/wiki/Bubble_sort" rel="nofollow noreferrer">bubble sort</a>.</p>
  
  <p>I've tried the following:</p>
  
  <p>1) The probability for an element A[<em>i</em>] > A[<em>j</em>] for <em>i</em> &lt; <em>j</em> can be calculated easily from the given probabilities.
  2) Using the above the I have calculated the expected number of swaps as:</p>
  
  <pre><code>double ans = 0.0;
  for ( int i = 0; i &lt; N-1; i++ ){
      for ( int j = i+1; j &lt; N; j++ ) {
          ans += get_prob(A[i], A[j]); // Computes the probability of A[i]&gt;A[j] for i &lt; j.
  </code></pre>
  
  <p>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[<em>i</em>] will be swapped with a number A[<em>j</em>].</p>
  
  <p>I have posted <a href="https://stackoverflow.com/questions/11331314/number-of-swaps-in-bubble-sort">a similar question</a> before but it did not had all the constraints.</p>
  
  <p>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.</p>