Write a function that efficiently counts the number of pairs of items that are swapped in a list of items L. The two items are swapped in L if i < j and L[j] > L[i]. That is, they are not ordered correctly. Call the function swaps, which takes the list as an argument. Use key as a parameter in the last part. The idea is that instead of comparing items directly as in a < b the sort will compare key(a) < key(b) instead. Give key a default value so that if it is omitted, the items are compared directly. One way to do this is to have a key function that returns the same item. For example, lambda x: x evaluates to such a function that could be used as a default value. One way to do this is using something like mergesort, where you find the number of swaps on the left and right (recursively) and then figure out the number of swaps that span the two sides while merging. Each time you add an item to the merged list from the right half, you know it is swapped with all the remaining items in the left half, so you can update the count accordingly.

Test with: testswaps.py

import unittest from swaps import swaps

class TestSwaps(unittest.TestCase): def testswaps_short(self): self.assertEqual(swaps([1]), 0) self.assertEqual(swaps([1,2]), 0) self.assertEqual(swaps([2,1]), 1) self.assertEqual(swaps([1,2,1]), 1) self.assertEqual(swaps([2,1,0]), 3)

def testswaps_allequal(self): self.assertEqual(swaps([2,2,2,2,2]), 0)

def testswaps_basic(self): self.assertEqual(swaps([5,2,3,6,9,8,7,1,4]), 4 + 1 + 1 + 2 + 4 + 3 + 2) # 5 is bigger than 4 numbers coming after it. # 2 is bigger than 1 number coming after it. # 3 is bigger than 1 number coming after it. # 6 is bigger than 2 numbers coming after it. # 9 is bigger than 4 numbers coming after it. # ... # ... # 4 is bigger than 0 numbers coming after it. # total swaps is 4 + 1 + 1 + 2 + 4 + 3 + 2

def testswaps_allbutone(self): n = 10000 L = [2] * n L.append(1) self.assertEqual(swaps(L), n)

L = list(range(n)) L.append(-1) self.assertEqual(swaps(L), n)

def testswaps_longsorted(self): n = 10000 self.assertEqual(swaps(list(range(n))), 0)

def testswaps_longreversed(self): n = 10000 self.assertEqual(swaps(list(reversed(range(n)))), (n * (n-1)) // 2)

def testkey_basic(self): L = list(enumerate([2,2,2,2,1])) key = (lambda x: x[1]) self.assertEqual(swaps(L, key), 4)

def testkey_longexample(self): n = 9987 L = list(range(n)) self.assertEqual(swaps(L, key = lambda x: -x), (n * (n-1)) // 2)

def testkey_weirderexample(self): evens_before_odds = lambda x: (x % 2, x) n = 1231 L = list(range(2 * n)) self.assertEqual(swaps(L, evens_before_odds), (n * (n-1)) // 2)

if __name__ == '__main__': unittest.main()