What is the shortest path to sort a list through item exchanging?
Recently, I met a math problem. I'd like to find an apporach to convert a list to ordered list by item exchanging with corresponding costs.
In short, the problem is as follows:
For a list [x1,x2,x3,x4,x5]
I'd like to sort it into a sorted list through item exchanging. That is to say I can only exchange the position of two item at each time. But there is a cost for exchanging items. The cost is calculated by multiply the distance and the difference of this two items.
cost = |xi -xj| * |i-j|
For example, given a list [3,2,9,1]
Path No.1: We first exchange 3 and 9, then 3 will be in the right position, the cost of this step is |9-3| * 2 = 12. Then the list becomes [9,2,3,1], we exchange 9 and 1 with the cost |9-1| * 3 = 24. So we get an ordered list with the total cost 36.
Path No.2: First exchange 3 and 1, which gives cost = |3-1| * 3 = 6, then we get [1,2,9,3]. Next, we exchange 3 and 9 to get a order lsit, which gives the cost = |9-3| * 1 = 6. Hence, the total cost is 12.
I found that we can always get the shortest path by first exchanging the smallest item to the right position. But my qusetion is about the reason. How to prove that this method always gives the shortest path even when the the original list goes longer(more than 4 item)?
Thanks a lot!!!