CODEWITHSUNDEEP
performancesorting
Bugaboo
Bugaboo

Reputation: 971

Costliest operation of sorting

What is the costliest operation of any sorting algorithm? Is it the swapping operation or the comparison operation?

I thought it was swapping but my friend thinks its the comparison. The only way I can justify that comparison is the costlier operation is that every element needs to be compared but not every element needs to be swapped (i.e if an element is already in the correct position, it does not have to be swapped). Therefore, overall in the bigger picture, there are more cheap comparisons than few costly swaps. But I am unsure of the answer. Any thoughts?

Upvotes: 1

Views: 618

Answers (1)

AdrienNK
AdrienNK

Reputation: 848

Assuming everything is done into RAM a swap operation is atomically faster than a comparison operation. (that's pretty obvious, 2 reads then a cpu operation versus 2 reads, 2 writes and everything in between including registry operations).

It clearly depends on your sorting algorithm, some do less comparisons because there are less elements, but swap comparatively more often.

Take quicksort that will do few comparison then swap pretty much everything and a simpler algorithm like bubble sort that with compare all the element with each other then swap less often. That also depends on the base array, if everything is already nearly sorted bubble sort won't swap anything but still compare everything while heapsort (for example) will still have to "swap" everything.

Finally the (avg number of swap operation)(time cost of swap operation)/(avg number of comp operation)(time cost of comp operation) is quite hard to estimate for an algorithm, and it's a lot more to extrapolate to all the algorithms.

I personally think that all in all the swap cost of any sorting algorithm is always higher than the comparison cost, but I can't back up that claim with any evidences (that's just a personal insight).

Upvotes: 1

Related Questions