Analysis

Full source code is available here.

We have an array of numbers. At any given time, there are two possible moves:

• Sort the first N – 1 numbers
• Sort the last N – 1 numbers

We are interested to know the minimum number of moves to sort the entire array.

On the spot, it might seems that there are a lot of possible combinations. However, you quickly realize that performing the same move multiple times does not change the array. If you sorted the first N – 1 numbers, sorting them again does not change the array so that would be a wasted move. To minimize the number of moves, a rationale thing to do if then always alternate between the two moves.

There are only two possible sequences of moves to consider:

• Order the first N – 1 numbers, Order the last N – 1 numbers, …
• Order the last N – 1 numbers, Order the first N – 1 number, …

Solution

The solution consist of counting the number of moves required to sort the entire array for each of the two sequences and return the minimum value.

First of all, we need a way to know when an array is sorted. We can do this with a simple method.

Follow the implementation of the algorithm.

We create two copies of the original array w1 and w2:

• w1 will be updated using the first sequence of moves
• w2 will be updated using the second sequence of moves

When count is zero, we run Array.Sort(w1, 0, n-1) on w1 and Array.Sort(w2, 1, n-1) on w2. This means that we sort the first N-1 elements of w1 and we sort the last N-1 elements of w2.

When count is one, we run Array.Sort(w1, 1, n-1) on w1 and Array.Sort(w2, 0, n-1) on w2. This means that we sort the last N-1 elements of w1 and we sort the first N-1 elements of w2.

We terminate the loop as soon as one of the two arrays is sorted and we return that value. This value must be the minimum number of moves required to sort the entire array.There is no point counting the number of moves required to sort the other array because we are only interested to the minimum.

Performance Analysis

The only concern here is the time complexity.

• How many moves are required to sort the entire array in the worse case scenario?
• What is the worse case scenario?

With ordering algorithms the worse case scenario is when the array is already sorted but in opposite order. The minimum and maximum number in the array are in the exact opposite locations. It is impossible to move them in the final location in a single move. This means that at least two moves are required to do so.

It is useful to split the array in three portions:

• The first location
• The middle area
• The last location

To move an element from a location to the opposite location, you must move it first in the middle area. When the element is in the middle area you can then move it to opposite location. With this in mind, it becomes easier to realize that the maximum number of moves to sort the entire array in the worse case is 3

The following diagram should make it clear.

Alternative Solution

With this consideration in mind you can write an alternative solution that does not require to actually do sorting operations but only checking where the minimum and maximum elements of the array are in the original array.

The possible number of moves can be 0, 1, 2 or 3:

• Return 0 if the array is already sorted.
• Return 1 if the minimum or maximum are already in the correct position
• Return 3 if the minimum or maximum element are in the opposite position
• Return 2 otherwise (both minimum and maximum are in the middle area)

This is the implementation of this alternative approach.

Personal Notes

My favorite implementation is the first one. I found that implementation quite elegant and easy to understand. It is also perfectly valid and pass all the TopCoder system tests. However, the alternative solution is really interesting. It was not the case for this particular problem, but sometimes more advanced problems requires a deeper level of understanding to find an acceptable solution.

When I first tried this problem, I solved it in a totally different and sub-optimal approach.

My idea was to determine which move to do based on the number of elements are lower then the first one and the number of elements greater then the last one. Don’t ask me how my mind come up with this solution. Anyway despite this solution is unnecessarily complex it still pass all system tests. I am always fascinated that you can solve a problem in so many different ways.

An other lesson learnt is that I forgot that the Array.Sort method allows you to sort subarrays. Using LINQ in this scenario was overkill.