Reference : https://discuss.codechef.com/questions/64884/wprob-editorial

The number of swaps an algorithm performs is equal to the number of inversions present in the input array.

The question is somewhat directly taken from the exercise of coremen

I'll solve this later first question :P

(a) Minimum number of swaps in **worst case**

This would occur when all the elements in the array would be present in descending order.

So, Number of inversions for 2=(9*3)=27

Number of inversions for 1 = (4*5)=20

0 would have no inversions.

So, total inversions=47

(b) The above configuration of the array will give the maximum number of swaps to sort the array.

Now coming to coremen exercise

We know insertion sort works by placing the unsorted element in it's correct position within sorted elements.

The running time of insertion sort depends on the number of inversions present in the array.

Assuming array has n distinct elements.

**Case A : Array is sorted in ascending order**

In this case, number of Inversions would be 0, so 0 swaps, however, a total of n-1 comparisons will still be made.

So, best case complexity comes out to be O(n).

**Case B: Array is sorted in descending order**

Total inversions come out to be

(n-1)+(n-2)+(n-3)+.......1 = $\frac{n(n-1)}{2}$ = O(n^{2}).

This will be exactly equal to the number of swaps and comparisons insertion sort will perform in this case.

So, worst case complexity comes out to be O(n^{2}).