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.

In-place sorting is essentially swapping elements without using extra storage, correct?

How can I find the minimum number of swaps required for a list?

A C D Q R Z   E   // input
| | | > > > <<<   // movement
A C D E Q R   Z   // output

Swapping:

A C D Q R Z E

swap Q with E, ACDERZQ
swap R with Q, ACDEQZR
swap R with Z, ACDEQRZ. done.

3 swaps.

Shifting items left or right is essentially swapping, but I want the optimal number for plucking an item out of line and switching its place with another.

share|improve this question
4  
Shouldn't this have been asked on SO? –  sbi Jan 4 '11 at 11:51
6  
This very much looks like homework... –  Xavier Nodet Jan 4 '11 at 12:39
1  
Maybe good for theoretical CS. –  Michael K Jan 4 '11 at 15:22
add comment

6 Answers 6

up vote 7 down vote accepted

Consider the problem of manipulating a list into a different state where you know the end state.

  1. Find each 'enclosed subgraph' bigger than one (I'll explain this later on).
  2. Find the sum of the lengths of the subgraphs and subtract the number of subgraphs.
  3. There's your answer for the number of swaps.

An 'enclosed subgraph' is a minimal subset of the whole where each item in the initial list is also in the end list.

So if you construct a subgraph with the indices 4,5 and 9 from the initial state and they have the values 10, 20 and 30 then for it to be an 'enclosed subgraph', you should be able to find the values from the end state with the indices 4, 5 and 9 and those values should be 10, 20 and 30 (though not necessarily in that order).

Consider this:

a b c d f e
    |
    v
b a d f c e

This would obviously take 3 swaps. (a <=> b, c <=> d, c <=> f)

Applying the algorithm above, it has:

  1. 3 'enclosed subgraphs', ([a,b], [c,d,f], [e])
  2. 2 subgraphs with more than one item ([a,b], [c,d,f])
  3. There are 5 items in all those subgraphs
  4. 5 - 2 == the answer.

It becomes a little more difficult when you want to do the minimal number of swaps to get it into sorted order, however, it is not impossible.

  1. Find the sorted order index of each item in the list, if you don't want to move any data, then this is n^2 time.
  2. Find the 'enclosed subgraphs'.
  3. Swap items in the list to get to the correct order, but only swap items within the same subgraph.

So, I hope you can see it's not impossible to do the minimal number of swaps to get to sorted order, but it's not worth it, because it requires a ridiculous number of comparisons. Just use heapsort.

share|improve this answer
1  
can you explain how does this work on "e d c a b"? According to your theory it will take only 1 swap to sort but actually it needs 3. –  Manoj R Jan 4 '11 at 7:57
    
There's 2 subgraphs [e, d, a, b] and [c]. so it's three. I'll update my answer to try to explain the 'enclosed subgraphs' better. –  dan_waterworth Jan 4 '11 at 8:11
    
Thank you for such a thoughtful answer! are there any whitepapers you could point me to? –  sova Jan 18 '11 at 2:26
    
Note that the value could be stated more simply as the length of the list, minus the number of enclosed subgraphs. –  augurar Dec 15 '13 at 19:00
add comment

How about a simple selection sort ?

  1. Find the min(A C D Q R Z E)
  2. Swap if min() != first element
  3. Repeat with (C D Q R Z E)
  4. Count the number of swaps.

On your example:

  1. ACD are already in order so no swap required.
  2. First swap required to put E in place
  3. R is min of QRZ, again swap to put it place
  4. Q is min of QZ, swap to put in place

... so simple without graphs :)

share|improve this answer
add comment

You are asking two completely different questions.

Or at the very least, you seem to think the amount of memory used has something to do with the speed, which isn't true.

In-place sorts just have a memory efficiency of 1 in Big O notation. That means: no matter how large the list, they'll still use the same amount of extra memory.

Optimum number of swaps

There are plenty of fast sorting algorithms (see this comparison list): particularly Heapsort, Quicksort, Merge sort, Timsort and Smoothsort. Out of these only Heapsort has a memory efficiency of 1 and it isn't always fastest.

Each algorithm will have varying efficiency depending on the list being sorted, so the speed always depends on the list and algorithm used. All you can do to measure the optimum number of swaps required to sort a list is to run it through each of those and record which one performed the fewest swaps.

This is only useful for academic research, though.

In practice if you're interested only in efficient sorting, you should already see that you can only see how fast it is to sort a list after it's already sorted so there's no benefit gained in testing before sorting. Just pick a search algorithm and stick with it: sometimes it will be the best choice, sometimes it won't. If you're only interested in sorts with memory efficiency 1 you've already got your answer: use Heapsort.

share|improve this answer
add comment

Not exactly, additional memory may be used but it is of constant size. computational complexity depends on the algorithm used.

share|improve this answer
    
Right, but I am interested in calculating the optimal number of swaps for going from ordering A to ordering B regardless of algorithm. Perhaps this is a deeper question than I thought. –  sova Jan 4 '11 at 6:22
1  
like i said it depends on the algorithm used. –  Pemdas Jan 4 '11 at 6:31
add comment

Most Algorithm listed in Wikipedia is optimized as constant space used, fewest iteration (comparison or code executed-wise). Maybe there are swap-optimized algorithm exists, but not in my knowledge.

Here is a quick solution I come up in mind. (Not Optimal, but good enough answers. You may need to enumerate the solution tree if you need optimal)

  1. Identify misplaced node, Let the count be M (Our worst case scenario)
  2. Run Several Algorithm and mark the swap they need, cut off if their swap > M
  3. Update the minimum M for different algorithm
  4. Repeat to 4, until you satisfy
share|improve this answer
add comment

How about this: Every time you swap two elements at indices i and j you record that as a tuple (i,j) somewhere. Once the list is sorted you bust out an abstract algebra book and read up on permutations, more specifically transpositions. There is a canonical cycle decomposition for permutations and once you have the canonical decomposition you can go about figuring out how to extract a minimal set of transpositions from it. I'm thinking of a greedy algorithm where you expand each cycle into a minimal number of transpositions and there should really be only one way of doing this but I'm not sure if this will give the minimal number of transpositions overall. My abstract algebra is not as good as it used to be so you might try asking this question on cs theory stack as well.

share|improve this answer
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.