CODEWITHSUNDEEP
arraysalgorithm
archit
archit

Reputation: 185

Minimum number of adjacent swaps

This is one of the question from online written test.

Books numbered from (1...N) have arrived to a warehouse.

The books are said to be best arranged if a book “i” is present only to the left of book “i+1” (for all i, 1 <= i <= N-1) and that book N is present to the left of book 1. [Yes! Any cyclic sorted sequence is a best arrangement]

Books received are in a random order.Now your task is to find out the minimal number of moves required to achieve the best arrangement described above.

Note that only valid move is to choose a pair of adjacent books and have them switch places.

For Example if the books were initially in the order 3 5 4 2 1

Solution can be

a. First swap the second pair of books: { result : 3 4 5 2 1 }

b. Swap the rightmost pair: { result : 3 4 5 1 2 }

So, in 2 moves we achieve the best arrangement.

I tried but not able to find out solution for this.First I though that i will divide the array in two arrays and then I will apply insertion sort on both the arrays but that is also not working. Please help me to find out a algo for this question.

Upvotes: 2

Views: 3002

Answers (1)

QuentinUK
QuentinUK

Reputation: 3077

N,1 can be anywhere in the sequence. eg 1..5, could be 3,4,5,1,2. So the first digit could be 1..5, ie 5x as complicated as Previous question. So, you'll have to do it 5 times. Use a sort algorithm that has a replaceable compare function.

So for the 3rd test the compare would be:-

// returns <0, 0 or >0
int compare(a,b){
     return ((b+N-3)%N) - ((a+N-3)%N);
}

Upvotes: 1

Related Questions