CODEWITHSUNDEEP
sorting
Lenar Hoyt
Lenar Hoyt

Reputation: 6159

SelectionSort and InsertionSort

I have to answer the following question: Could you think of a scenario in which SelectionSort is better (in terms of the development of the result) than InsertionSort.

My idea is that if you only need e.g. the top 10 of a very big list, your could end the sorting after the 10th step. Is this a valid answer to this question? Could you think of other scenarios?

Upvotes: 0

Views: 721

Answers (2)

Grook
Grook

Reputation: 405

When input array is "close to sorted" selecion sort have better performance than insertion sort. Also there are two things you must take in mind: selection sort needs only Θ(n) swaps versus Ο(n2) (in case of insertion sort) swaps; selection sort has stability strong realization, insertion sort has no.

Upvotes: 1

jeha
jeha

Reputation: 10720

InsertionSort has Ο(n^2) swaps in worst case, but SelectionSort is Θ(n). So if writes are significantly more expensive than reads, SelectionSort is better suited.

Upvotes: 2

Related Questions