Sorting with a minimal number of swaps

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

Sorting with a minimal number of swaps

Post by maxdiver » Sun May 24, 2009 5:40 pm

The problem is, given an array A[1..N] of numbers (not necessarily different) output a minimal number of swap operations (you can swap any, not only neighbour, elements) needed to make this array sorted.

If all numbers A were different, then the solution is obvious: 1) count the number of inversions, or 2) go through the first element to the last, and if the current element differs from needed - then swap current element with the needed and answer++.

But when there may be several instances of the same number, then difficulties appear: we don't know which of the copies to swap. For example, "2 1 1" - here we should swap 2 and the second 1.


Maybe (I speak about algorithm 2) ), if there are several choices, then we should always swap with the last one?..

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Sorting with a minimal number of swaps

Post by mf » Mon May 25, 2009 7:44 am

Did you find this problem at some online judge or contest, or you're just curious?
If all numbers A were different, then the solution is obvious: 1) count the number of inversions

Number of inversions is useful if we are allowed to swap only adjacent elements.

or 2) go through the first element to the last, and if the current element differs from needed - then swap current element with the needed and answer++.

Yeah, that works. And let's try to understand exactly why it works:

Let's draw a directed graph, whose vertex set is the set of elements and there's an edge from each B to A, for i=1..N, where B is sorted array A. When all elements are distinct, this graph is a collection of disjoint cycles - it's just the cyclic decomposition of permutation of elements. Each swap either splits a cycle into two (when swapped elements are part of the same cycle), or joins two cycles, and so it either increments or decrements number of cycles. Array becomes sorted when there are n cycles, so the lowest bound on number of swaps is n - c, where c is the initial number of cycles. In the algorithm described above each swap always increases number of cycles, so it achieves this lowest bound.

If elements are not unique, this graph has a lot more complex structure - it can be any Eulerian graph. And it seems to me that minimum number of swaps will be n - c, where c is the maximum number of cycles into which graph's multiset of edges can be partitioned, but this turns out be an NP-hard problem [1]!

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

Re: Sorting with a minimal number of swaps

Post by maxdiver » Mon May 25, 2009 11:34 am

mf

I'm just curious :)
I tried to find this problem in online judges, but found only the "easy" version.
Number of inversions is useful if we are allowed to swap only adjacent elements.
Yeah, you're right. It was a wrong move from the algorithm 2) to algorithm 1) :)
Yeah, that works. And let's try to understand exactly why it works ...
Thanks, I'll think about it...

drumair
New poster
Posts: 1
Joined: Thu Jan 08, 2015 1:56 pm

Re: Sorting with a minimal number of swaps

Post by drumair » Thu Jan 08, 2015 2:10 pm

it was the problem at first...
We are the leading the world in providing best ccna gre and link prep solutions. Our incredible offers ccie written and computer training center gedare accessible at reasonable prices; our principiacollege.edu selftestengine ged is very rare in IT world.

Post Reply

Return to “Algorithms”