Proving greedy algorithm for largest permutation with at most K swaps

Question

Let's see the following statement:

Given an array with the first N natural numbers in any order perform at most K(non-negative) swaps in order to obtain the largest possible permutation.

For making the statement more understandable let's say that an array starting with [20, ...] is greater than one starting with [9, ...], so we care only about the value.

Let's consider now the following greedy algorithm for this problem:

While you have swaps try to put the largest numbers in decreasing order from left to right. If a number is already in its position(according to the algorithm) we don't count a swap.

Here an example: [1, 5, 4, 3, 2] with K = 2, answer would be [5, 4, 1, 3, 2].

I was trying to prove this algorithm, but I couldn't find something strong enough. I know that with K swaps we can put at least the largest K number at the beginning, but depending on de input we can have more, and in some cases with one swap we can set 2 numbers at once.

I would appreciate if someone can provide a prove for that algorithm or even another solution for the problem.

Thanks in advance.

Answer 1

depending on de input we can have more, and in some cases with one swap we can set 2 numbers at once.
I don't think that would be the case.

I think you understand the main part of why the algorithm works, but are confused by this case.

If you set a higher number to its correct position first, and some another number also gets to its correct position ("by accident") as a consequence of the same swap,
then this case, in fact saves us one swap, because when we will reach the position of that element which was "set accidentally", we don't need to count any swap that time, and we can simply move forward to next position (right).

And also, its not clearly mentioned in your description of the algorithm, so I also clear that -
The swaps you perform during any steps, are also to be reflected in the given array in each step dynamically.

Answer 2

It can be proven that it will take at most K swaps (where K is a natural number $N>K$ inductively.

First consider the situation. $N=1$. The array is the largest possible permutation since it is the only possible permutation.

For the inductive step assume that it takes $K$ swaps to permeate an array of size N ($N>K$) to it's largest form. Consider an array of length $N+1$ if you swap the largest element to the front then at most you have added one swap step, however you now have an array of length N. We know that this will take at most $K$ swaps so it must take at most $K+1$ swaps to do an $N+1$.

By induction the number of swaps done must me at most $K$ swaps where $N>K$.