Question: Implement an algorithm that counts the inversions of your linked list structure (see section 1.2). For full points the algorithm should have linearithmic worst-case time complexity (else 10P reduction). Extend your BubbleSort implementation to count the number of calls to Swap and compare with the result of your inversion count. Make sure the result matches with the information from section 1.2.

Please explain your code in detail :-)

Algorithm 1 BubbleSort Require: a is a list data structure of length n>0. swapped true while R 20 and 8Wapped = true do swapped false for i 0 to R do if ali]> ali+1] then true SWAP(a, i, i +1) end if end for RR-1 end while Ensure: a is an ordered permutation of a. Stable Sorting Let a be a list data structure of length n>0.Furthermore let S be a sorting algorithm and a be the ordered permutation of a after applying S according to the total order relation with associated equality relation = We call S 8table if and only if for all z, y with ali]s z=y-aj] and i 0 and let i,j e {0,...,n-1) with i a[j] Example Consider indexes: (0,1,2,3,4,5) a-(1,2,4,3,5,0) then a has the following inversions: set of inversions: {(0,5), (1,5), (2,5), (2,3), (3,5), (4,5)) values of the inversions: 10), (2,0), (4,0), (4,3), (3,0), (5,0)) Notice that the inversions are the pairs of indices, not pairs of values. The reason is of course that indices are unique, while value are not necessarily unique