Minimal shift operations to sort an array

Question

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?

• 喜欢算法和数学: 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.
• 喜欢算法和数学: 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.

Answer 1

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.