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.
Please look at this example:

4 3 2 1 -&gt; 3 2 1 4 -&gt;   3 comparisons
3 2 1 4 -&gt; 2 1 3 4 -&gt;   2 comparisons
2 1 3 4 -&gt; 1 2 3 4 -&gt;   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) =&gt;  n(n-1)/2/(n-1) =&gt; (n-1)

NOTE : (n-1) is number of steps
is it right?
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 &lt; j$ where $A_i &gt; A_j$. By linearity of expectation, the expected number of comparisons is thus
$$
N - 1 + \sum_{i &lt; j}P(A_i &gt; A_j) = N - 1 + \frac{N(N - 1)}{4}
$$