Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Problem Statement -

Problem Statement

The task is to find the minimum number of swaps required in the given arrangement of cartons to get the desired arrangement of cartons. Only adjacent cartons can be swapped.

I have tried an ad hoc approach, but it proved inefficient towards the upper limit of the data range. Here it is for reference -

Traversing through the given arrangement of cartons
 if position of carton>than the desired position
  swap back
  go to previous iteration

What would be a pragmatic approach to the problem?

Test Data Range - N<=105

Source - INOI 2009 Q Paper

share|improve this question
    
in other words you want to find the most efficient bubblesort... –  ratchet freak Dec 25 '12 at 23:54
1  
Reason for down-voting? @ratchetfreak I find bubblesort per se inefficient. I am trying to find an algorithm that can handle such large data-sets in an efficient way. –  7Aces Dec 26 '12 at 5:29
1  
@ratchet freak: I am not sure this is bubble sort: in bubble sort you repeatedly scan an array and perform the swaps during each scan. Here you want to find a minimal sequence of swaps that produces a solution. Seems like a problem that can be solved using streams and lazy evaluation. –  Giorgio Dec 26 '12 at 10:26
1  
@7Aces: I also do not understand the down vote and the votes to close. The question is very clear (and IMHO, interesting too): find an algorithm that computes an optimal solution. Upvoting and voting to keep open. –  Giorgio Dec 26 '12 at 10:28
    
Here is the solution - stackoverflow.com/questions/7797540/… –  Petar Minchev Dec 26 '12 at 10:34
show 1 more comment

1 Answer

with only adjacent swaps you are limited to a O(n^2) sorting algorithm, (with worst case being a reverse sorted set)

and since you only have to limit yourself to least amount of swaps you can compare everything as much as you like

one way to guarantee the least amount of swaps is to only swap 2 cartons when they are in reverse order

both bubble sort and insertion sort will do this

the way to compute this minimum is to find the desired location of each carton (with any sorting algo) and take the sum of the amount each carton is shifted and divide by 2

in psuedo code

sort arr
sum=0
foreach c in arr
   sum+= abs(oldIndexOf(c)-indexOf(c))
return sum/2
share|improve this answer
    
An algorithm with a O(n^2) time complexity is just not efficient enough to solve the data ranges in the time limit. The most efficient algorithm for this possesses O(n log n) time, see - stackoverflow.com/questions/7797540/…. The algorithm provided resorts to O(n^2) complexity as it finds oldindex(c) with every iteration. –  7Aces Dec 26 '12 at 15:30
1  
@7Aces, oldindex(c) is an O(1) operation if you store it in a hash table. –  Karl Bielefeldt Dec 26 '12 at 16:13
1  
@KarlBielefeldt Thanks for the tip! Still, incorrect algorithm. Gives incorrect output for the test case - O={1,2,3,4,5,6} R={6,5,4,3,2,1}. Output - 9 (Should be 15) –  7Aces Dec 26 '12 at 19:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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