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.

So far, most of the fastest and common sorting method is quicksort. Although it has its pro and cons. However, i'm thinking that although this sorting method is fast but does it provide shortest swapping step? Because quicksort divide a set of element into 2 and then sorting, will it double up the swapping step?

share|improve this question
    
There are more sophisticated sorting algorithms than quicksort... –  FredOverflow Sep 14 '11 at 18:25
add comment

3 Answers

up vote 7 down vote accepted

will it double up the swapping step?

In most cases: The contrary. I'll assume that by swapping you refer to the total number of comparisons. Swapping doesn't really matter in my opinion as it should be a constant time operation and as it is the result of a comparison. The number of comparisons is important.

By dividing the set into two halves you can always think of it as a binary tree. The amount of comparisons to be done is thus logarithmic and dependent on the height of this tree. However, for quicksort, this is not true for all input vectors. When the input is already sorted and the wrong pivot is chosen, then quicksort will run in O(n^2) which is terribly slow. You can think of it as a pretty high tree because quicksort could not properly divide the input vector. Worst case: Not swaps at all and costly at runtime.

Generally you can say, the number of swaps is related to the number of comparisons. The fewer comparisons, the fewer swaps. The number of swaps always depends on the specific input vector!

share|improve this answer
    
Neat and compact! –  Emmad Kareem Sep 14 '11 at 11:13
2  
I would add that selection sort and insertion sort are very similar feeling algorithms, but selection sort only ever requires O(n) swaps, while insertion sort may require O(n^2) swaps. (Both require O(n^2) comparisons.) Also, there are derandomized forms of quick sort (using the median of 5 technique) that will always perform at O(n lg n). (BTW, +1). –  Macneil Sep 14 '11 at 11:23
    
@Falcon, as u mention, 'the number of swaps is related to the number of comparisons. The fewer comparisons, the fewer swaps. The number of swaps always depends on the specific input vector'. so how about the performance guarantee of selection sort in term of swapping? worst-case should be n-1 swap, best case is? 1?so the performance guarantee in term of swapping is (n-1)/1 = n-1? –  m11 Sep 20 '11 at 12:51
    
@m11: AFAIK Selection Sort has no best and no worst case when it comes to swapping. The algorithm always swaps n-1 times and has thus always O(n) swaps. But sometimes it swaps an item with itself (which is still a constant time operation imho, even if a compiler can optimize it away in some cases). –  Falcon Sep 20 '11 at 16:24
add comment

On average Quicksort sorts an array in n(log n) time (which is almost as good as it gets). In worst case it takes n² (but this happens rarely).

Another common sorting algo that takes n(log n) time to sort is Merge Sort. You'll notice that both use the "Divide and Conquer" method, but each with a different strategy.

As for swapping steps, it depends on how each algorithm is implemented. For instance, the number of steps on Merge Sort depends heavily on how you implement the Merge function (e.g., you could merge in place, use an auxiliary array, etc).

Overall it's assumed that the constant factors (swap steps, comparisons and so on) are smaller on Quicksort, though, so it's usually preferred over Merge Sort.

Finally, comparing the number of swap steps with slower algorithms, like Insertion or Bubble sort, makes no sense in my opinion, because the running time has a much more important role.

share|improve this answer
    
instead of comparing running time, if just comparing the swap steps, which mean that those slowest algorithm such as selection sort, bubble sort will somehow less swapping step than quicksort or mergesort, am i right? –  m11 Sep 14 '11 at 11:13
    
@m11: Imho that'll never be the case, but I haven't calculated it. Some algorithm that requires more comparisons will inevitably swap more often. Maybe some math pro can provide some good asymptotic bounds for the number of swaps of various algorithms. –  Falcon Sep 14 '11 at 11:49
add comment

The presentation provided in the link show the number of swaps of different sort algorithms using the O notation. I hope that this could help you.

Power point presentation for different sort alg. showing complexity

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.