Bubble sort number of swaps

Question

To sort a list of 6 elements {11,5,7,3,2,1} using the bubble sort algorithm, you can manually find this to have 14 swaps. I know the following formula gives comparasons

n(n-1)/2

6(6-1)/2 = 15. Why 15 and not 14?

Also, is there a similar formula for Quick sort and Insertion sort?

Thanks in advance!

Answer 1

In ascending order:

In Bubble sort, the largest element moves to the right. So swapping is done, when a smaller element is found on the right side.

So to count the number of swaps for an element, just count the number of elements on the right side that are smaller than it.

Array{11,5,7,3,2,1}

For 11, the number of elements on the right side which are smaller: 5(5,7,3,2,1)

for 5: 3(3,2,1)

for 7: 3(3,2,1)

for 3: 2(2,1)

for 2: 1(1)

for 1: 0

total swaps: 5+3+3+2+1 = 14