2
$\begingroup$

Let's say we have a function shift(array[], int s) which swaps the position of array[s] to array[0] and shifts all other elements to the right. For example:

array = {1,2,3,4,5,6} --> shift(array, 3) --> array = {4,1,2,3,5,6}

If you were to sort an array consisting of numbers 1..n using only the function shift, what would be your approach in order to use shift() the least amount of times?

I've tried many solutions, but nothing which would fit all types of arrays. For an array like {3,4,2,5,1} a good idea would be marking all elements which are smaller than the element behind them as not in their place, and then shifting the biggest marked element, like this:

{3,4,2,5,1} --> {2,3,4,5,1} --> {1,2,3,4,5} function called 2 times.

But this algorithm would lead to a disaster when called on an array like this: {1,9,7,2,5,4,8,6,10,3}. It seems like the best solution would be simply putting the biggest element at the start of the array, and then putting the element smaller by 1 behind it, so calling the function as many times as the size of the array. There's gotta be some sort of solution which works for every type of input which I'm just not seeing?

$\endgroup$
2
  • $\begingroup$ Would you not aim for a combination of shifts that causes the least amount of elements to be shifted? Rather than the least amount of shifts? $\endgroup$ Commented Dec 12, 2021 at 9:24
  • 1
    $\begingroup$ @Michel surprisingly, both tasks lead to the same combination of shifts! $\endgroup$
    – nir shahar
    Commented Dec 12, 2021 at 13:29

1 Answer 1

1
$\begingroup$

The short answer

You can barely do any better than just the naive solution. To be a bit more precise, let $p_i$ be the position of the $i$'th largest element. Then if for some $k$ we have that $p_k>p_{k+1}$, but for all $m > k$ it holds that $p_{m}<p_{m+1}$ - then you will need exactly $k$ function applications.

The long answer

(Assuming you read the "short answer") Why would this be the case?

This $k$ is special - its the largest element that is not in its place. Notice that applying shift to $k+1$ will only decrease $p_{k+1}$ and since we already assumed that $p_{k}>p_{k+1}$ this will also hold after applying the function and hence wont fix the relative position between $k$ and $k+1$ (which needs to be fixed for the array to be sorted).

In addition, applying the function to any other value which is not $k$ or $k+1$ cannot change their relative positions (directly follows from the definition of the function).

Hence, one must apply the function on $k$ at some point in time. But now $p_k=0$ and hence it has to be true that $p_{k-1}>p_k$.

I believe you can see how this continues now - you will have to apply the function on $k-1$ and then on $k-2$, and so on.

This also gives you the exact order you need to apply the function in. Therefore, this exact order is the absolute best you can ever do - and will require exactly $k$ times to apply a shift.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.