minimum switch to sorted permutation

Question

Suppose I have an array like this: [5 4 1 2 3]

And I want to compute the minimum switch I have to make to sort the unsorted permutation.

Now the answer is 7 in this case. Just move 4 and 5 to the right, or move 1, 2, 3 to the left.

The irony though, is that I used [4 5 1 2 3] in my notes, which gives 6, and mislead myself and make a fool of myself.

Steps:

[5 1 4 2 3] // step 1

[1 5 4 2 3] // step 2

[1 5 2 4 3] // step 3

[1 2 5 4 3] // step 4

[1 2 5 3 4] // step 5

[1 2 3 5 4] // step 6

[1 2 3 4 5] // step 7

I've thought of things like having an array that keep the offset needed, and for each loop, just look for the switch that moves the whole thing closer to goal.

But that just seem too slow, any ideas?

EDIT: from comment: are the members of the array guaranteed to completely belong to {1..N} set for an array of size N, without repeating numbers?

Nope. It's not guaranteed not to repeat or being in [1...n] for array sized N.

UPDATE:

There are two solutions to this particular problem, once is slower but more straightforward bubblesort, another is the faster but less straightforward mergesort.

With bubblesort, you basically count the number of switches when running the algorithm.

With mergesort, it's a bit more trickier, but the counting happens when merging. When the array is already merged, the count should yield 0 as no switches will be needed to sort this array. With bubblesort, you count the switches when you push the largest or the smallest number to the left or right. With mergesort, you count switches when merging. I bit of hand writing brute forcing will get you there.

Answer 1

What you're actually looking for is calculating the number of inversions in a sequence.

This can be done in O(n*logn) using mergesort, for example.

Here you have an article about this subject, looks quite understandable.

Some more links:

• https://stackoverflow.com/a/338252/2180475
• https://codereview.stackexchange.com/questions/12922/inversion-count-using-merge-sort

Answer 2

This looks suspiciously similar to bubble sort, in which you need up to n^2 movements.

And the interesting fact is that, simple bubble sort actually achieves your goal to find the minimum number of switches! (proof below)

In that case, we don't need to further improve algorithms using double loops, and it's actually possible using double loops (in C++):

int switch = 0;
for(int repeat=0; repeat<n; repeat++){
    for(int j=0; j<n-repeat; j++){
        if(arr[j]>arr[j+1]){
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            switch = switch + 1
        }
    }
}

The switch is the result.
arr is the array containing the numbers.
n is the length of the array.

Prove that this produces minimum number of switch:

First, we note that the bubble sort essentially moves the highest element into the rightmost position in the array at each iteration (outer loop)

Note that switching the highest element with any other element in the process does not change the relative order of other elements. And also any other switch operations done in between our attempt to move the highest element to its position will not change the number of switch required to move the highest element to place. And so we can interchange the switch operations such that the highest element is always switched first until it gets into position. Therefore switching the highest element into its position one at a time is optimum.