Average number of swaps performed in Bubble Sort

Question

I came across this problem right now: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3155 The problems asks to calculate the average number of swaps performed by a Bubble Sort algorithm when the given data is a shuffled order of first n (1 to n listed randomly) natural numbers.

So, I thought that:

1. Max no of swaps possible=n(n-1)/2. (When they are in descending order.)
2. Min no of swaps possible=0. (When they are in ascending order.)

So, the mode of this distribution is (0+n(n-1)/2)/2 =n(n-1)/4. But, this turned out to be the answer. I don't understand why did the mode coincide with mean.

Answer 1

Since the inputs to be sorted can be any random number with equal probability of occurrence, the distribution is symmetrical.

It is a property of symmetrical distributions that their mean, median and modes coincide which is why the mean and mode are same.

Answer 2

Every swap reduces the number of inversions in the array by exactly 1.

The sorted array has no inversions, thus the number of swaps is equal to the number of inversions in the initial array. Thus we need to compute the average number of inversions in a shuffled array.

The pair of indices i, j, with i < j, is an inversion in exactly half of the shuffled arrays. There are n * (n-1) / 2 such pairs, thus we have n * (n-1) / 4 inversions on average.