# Bubble sort: average number of total key comparisons

I want to know the steps for finding a Formula for Average number of total comparisons in bubble sort.

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?

• (I see a buble, more important: what is bubble descending sorting/mode? average of/over what?) – greybeard May 2 at 14:51
• @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 – jasmine May 2 at 15:00
• 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 – jasmine May 2 at 15:07
• An average with respect to which input distribution? – Steven May 2 at 15:16
• @Steven YES exactly – jasmine May 2 at 15:17

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}$$