0
$\begingroup$

I have been stuck on this sorting problem for a while now:

Given an array of length N find the minimum number of shift operations in order to sort the array. A shift operation is defined as shifting a value in an array to another position. For this problem however, you can only perform this shift operation on the first element in the array.

For example, let's say N = 4 and our array was [1,2,4,3].To sort this array we could perform the following shift operations:

[1,2,4,3] -> [2,4,1,3] -> [4,1,2,3] -> [1,2,3,4]

Thus, we would have to perform a minimum of 3 shift operations.

Any clues on how to approach this problem?

$\endgroup$
2
  • 1
    $\begingroup$ Please add a reference to the original problem. Why is this important? Reasons. 1) Credit should be attributed. 2) The original problem might have other or more related materials, such as examples, hints, test cases and similar problems. 3) A reference is apt to motivate people. $\endgroup$
    – John L.
    Jan 20 '19 at 4:40
  • 1
    $\begingroup$ What have you tried so far? This site encourages you to show your thoughts or partial progress toward solving the problems. People could then make the answers more helpful for you and for future readers. $\endgroup$
    – John L.
    Jan 20 '19 at 4:41
1
$\begingroup$

The problem is actually quite simple. When shifting the element at the front, find the last element that is greater than it, and put it after that element.

The number of shifts this takes is $n -k$ where $k$ is the length of the longest increasing suffix of the input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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