Selection Sort vs Insertion Sort For Reversed Array

Question

I had a question in a test, which asked me the following question:

Selection sort runs faster than Insertion sort for an array in reverse order.

Now, according to my knowledge, both of them have a time complexity of $O(n^2)$ in case of this particular input arrangement, so comparing the running time of them is not possible because it becomes a question of how the algorithms are implemented. A poorly written selection sort could be much slower than insertion sort and vice versa, so an argument can be made for both cases.

But the answer key says that since selection sort has lesser number of swaps (order of $n$) compared to insertion sort (quadratic comparisons), selection sort should be faster than insertion sort for this particular case.

Which is the correct solution? Can selection sort be faster under certain assumptions?

Answer 1

This is an awful question for a test.

Selection sort always has about n^2/2 comparisons and n swaps. Insertion sort has between n and n^2/2 comparisons and the same number of swaps. But as you said absolutely correctly, the actual time depends on the exact implementation.

For example if you look for the smallest element in selection sort like this:

smallest = a[k]
smallestIndex = k
for k+1 ≤ j ≤ n
 if a[j] < smallest
 smallest = a[j]
 smallestIndex = j

you see that that the code in the if-statement will be executed with every execution of the loop.

On the other hand, in the insertion code the moving can be done with some highly optimised code.

So I wouldn't be at all surprised if insertion sort were faster on some particular implementation even in this situation, even though it is the worst case for insertion sort. (I would also not be surprised if selection sort were faster).

• Tassle: To add to your answer, in a scenario where comparisons are expensive but swaps are almost for free (it can happen) you could implement insertion sort with binary search an get n*log(n) comparisons, making it miles better than selection sort.