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?
does quicksort provide less swapping step?
algorithms;sorting
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!