0
$\begingroup$

I want to know the steps for finding a Formula for Average number of total comparisons in bubble sort.
Please look at this example:

4 3 2 1 -> 3 2 1 4 ->   3 comparisons
3 2 1 4 -> 2 1 3 4 ->   2 comparisons
2 1 3 4 -> 1 2 3 4 ->   1 comparisons

For ordered and reverse ordered input we have different formula for number of total comparisons:

Min = n-1
Max = n(n-1)/2

And I want a formula with steps to get average of it - all possible inputs - / expected number of key comparisons for each of n input values selected from a uniformly random source

My try

(Sum of total comparisons)/(n-1) =>  n(n-1)/2/(n-1) => (n-1)

NOTE : (n-1) is number of steps

is it right?

LOOK AT THIS I wrote everything

$\endgroup$
10
  • $\begingroup$ (I see a buble, more important: what is bubble descending sorting/mode? average of/over what?) $\endgroup$ – greybeard May 2 at 14:51
  • $\begingroup$ @greybeard In this example the array is totaly descending i mean all of the numbers should be sorted 4 3 2 1 . so when we have this array we have different formula for sum of Comparisons and we have min max and average in this form but if we do'nt have descending array like : 3 1 2 4 we have different formula for Comparison we have just N( N-1 )/2 and no min or ave or max form $\endgroup$ – jasmine May 2 at 15:00
  • $\begingroup$ So we have 2 forms of buble sort : 1- it isn't totaly Ordered or Disordered like 2 3 1 4 and 2- totaly ord or disord like : 1 2 3 4 and 4 3 2 1 $\endgroup$ – jasmine May 2 at 15:07
  • $\begingroup$ An average with respect to which input distribution? $\endgroup$ – Steven May 2 at 15:16
  • $\begingroup$ @Steven YES exactly $\endgroup$ – jasmine May 2 at 15:17
0
$\begingroup$

I'm assuming that all elements in the array you're sorting are distinct.

The average number of comparisons over all permutations of the array is equal to the expected value of the number of comparisons, so let's calculate that instead.

The total number of comparisons done to sort some array $A$ (length $N$) is equal to $N - 1 + (\text{Number of inversions in } A)$, where an inversion is a pair of indices $i < j$ where $A_i > A_j$. By linearity of expectation, the expected number of comparisons is thus $$ N - 1 + \sum_{i < j}P(A_i > A_j) = N - 1 + \frac{N(N - 1)}{4} $$

$\endgroup$
2
  • $\begingroup$ What, as per question, are the steps for finding such? $\endgroup$ – greybeard May 4 at 11:25
  • $\begingroup$ @Andi Qu thank you so much $\endgroup$ – jasmine May 4 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.