SP1526 RSORTING - Ranklist Sorting

You are given the scores of several players in a competition. Your task is to create a ranklist of the players, sorted in decreasing order by score. Unfortunately, the data structure used for the list of players supports only one operation, which moves a player from position i to position j without changing the relative order of other players. If i > j, the positions of players at positions between j and i − 1 increase by 1, otherwise if i < j the positions of players at positions between i + 1 and j decrease by 1. This operation takes i steps to locate the player to be moved, and j steps to locate the position where he or she is moved to, so the overall cost of moving a player from position i to position j is i + j. Here, positions are numbered starting with 1. Determine a sequence of moves to create the ranklist such that the sum of the costs of the moves is minimized.

N/A

N/A