Sort deck of cards with least no of moves

Question

We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

4 3 1 2 
3 4 1 2
2 3 4 1
1 2 3 4

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

2 3 1 4 
1 2 3 4

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2

Answer 1

Given a permutation $\pi:[n]\to[n]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

1. $c \leftarrow n$
2. for each $k$ from $n$ down to $1$ do
3. $\space\space\space$ if $c = \pi(k)$ then
4. $\space\space\space\space\space\space$ $c \leftarrow c - 1$
5. $\space\space\space$ end if
6. end for
7. return $c$

In other words, choose the highest card, for which there is another card of higher value in front of it. More formally, choose a maximum $c\in[n]$ such that there exists a $c' > c$ with $\pi(k') = c'$, $\pi(k) = c$ and $k' < k$. Clearly, this card is not in order yet and since it is the one with the highest value it must be moved first if we want to keep the number of moves minimal. For the permutation $3,1,4,2$ this card is clearly card number $2$.

Answer 2

use Count sort

for x in input:
    count[key(x)] += 1

# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount

# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1

return output

sorry about that. in that case you can pick the first greatest card which is smaller than the top card and move it to top. with this the above example i.e. 4 3 1 2 can be done in three steps and this one 2 3 1 4 in ONE step..