Sort a set of disks in minimum number of moves

Question

So this question is more of an algorithm/approach seeking question where I'm looking for any thoughts/insights on how I can approach this problem. I'm browsing through a set of programming problems and came across one question where I'm required to provide the minimum number of moves needed to sort a list of items. Although this problem is marked as 'Easy', I can't find a good solution for this. Your thoughts are welcome. The problem statement is something like this.

X has N disks of equal radius. Every disk has a distinct number out of 1 to N associated with it. Disks are placed one over other in a single pile in a random order. X wants to sort this pile of disk in increasing order, top to bottom. But he has a very special method of doing this. In a single step he can only choose one disk out of the pile and he can only put it at the top. And X wants to sort his pile of disks in minimum number of possible steps. Can you find the minimum number of moves required to sort this pile of randomly ordered disks?

Answer 1

The easy way to solving it without considering making minimum moves will be: Take a disk that is max value and put it on top. And then take the second max and put it on top. And so on till all are sorted. Now this greedy approach will not always give you min steps.

Consider this example: [5,4,1,2,3] with the above greedy approach it will be like this:

[5,4,1,2,3] 
[4,1,2,3,5]
[1,2,3,5,4]
[1,2,5,4,3]
[1,5,4,3,2]
[5,4,3,2,1]

Which takes 5 moves, but the min moves should be this:

[5,4,1,2,3]
[5,4,1,3,2]
[5,4,3,2,1]

Which takes only 2

To get min moves, first think how many values are already in descending order starting from N, you can consider those something you don’t need to move. And for the rest you have to move which is the min value. For example

[1,5,2,3,10,4,9,6,8,7]

Here starting from 10 there are in total 4 numbers that are in desc order [10,9,8,7] for the rest you need to move. So the min moves will the 10-4 = 6

[1,5,2,3,10,4,9,6,8,7]
[1,5,2,3,10,4,9,8,7,6]
[1,2,3,10,4,9,8,7,6,5]
[1,2,3,10,9,8,7,6,5,4]
[1,2,10,9,8,7,6,5,4,3]
[1,10,9,8,7,6,5,4,3,2]
[10,9,8,7,6,5,4,3,2,1]