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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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!
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.
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.