A list contains the numbers in some order. In each step, you can swap two adjacent numbers. Your task to order the list so that all the numbers in the first half are smaller than all the numbers in the last half. What is the smallest number of swaps you need?
The time complexity of the algorithm should be . You may assume that is even.
In a file semisort.py
, implement a function solve
that returns the smallest number of swaps.
def solve(t): # TODO if __name__ == "__main__": print(solve([2, 1, 4, 3])) # 0 print(solve([5, 3, 4, 1, 6, 2])) # 6 print(solve([6, 5, 4, 3, 2, 1])) # 9 print(solve([10, 1, 9, 2, 8, 3, 7, 4, 6, 5])) # 15
Explanation: On the list , the numbers in the first half, and , are already smaller than the numbers and in the last half. The list needs at least swaps. Here is one optimal sequence of swaps: