What type of input differentiates insertion sort from selection sort?

2
votes

  1. In what kind of test case does insertion sort perform better than selection sort? Clearly describe the test case.

  2. Why does selection sort perform worse than insertion sort in that test case?

I answered the first question like this:

O(n2). When insertion sort is given a list, it takes the current element and inserts it at the appropriate position of the list, adjusting the list every time we insert. It is similar to arranging the cards in a card game.

And the second question:

Because Selection Sort always does n(n-1)/2 comparisons, but in the worst case it will only ever do n-1 swaps.

But I am not sure about my answers, any advice?

1
sortingtime-complexityinsertion-sortselection-sort
You didn't give a test case for question one. – Kevin
Maybe I don't understand what test case is, can you please explain it to me? – r4b
They want something like "performance is worse for selection sort when the input list is already sorted in descending order, for example [4,3,2,1]". (I don't know if that's actually true, that's just an example of the format of the answer) – Kevin
As it stands, your question has nothing to do with Python really; certainly attaching a version-specific tag is premature. You are talking about the theory of sorting, not the implementation of either algorithm. – Martijn Pieters

1 Answers

3
votes

For a case where insertion sort is faster than selection sort, think about what happens if the input array is already sorted. In that case, insertion sort makes O(n) comparisons and no swaps. Selection sort always makes Θ(n2) comparisons and O(n) swaps, so given a reasonably large sorted input array insertion sort will outperform selection sort.

For a case where selection sort outperforms insertion sort, we need to be a bit tricky. Insertion sort's worst case is when the input array is reverse sorted. In this case, it makes Θ(n2) comparisons and Θ(n2) swaps. Compare this to selection sort, which always makes Θ(n2) comparisons and O(n) swaps. If compares and swaps take roughly the same amount of time, then selection sort might be faster than insertion sort, but you'd have to actually profile it to find out. Really, it boils down to the implementation. A good implementation of insertion sort might actually beat a bad implementation of selection sort in this case.

As a tricky solution, try making a custom data type where compares are cheap but swaps take a really, really long time to complete. That should work for your second case.