CODEWITHSUNDEEP
algorithmsortinginsertion-sortselection-sort
starrr
starrr

Reputation: 1023

Is selection sort faster that insertion sort in reverse arrays?

In the case that we have a reversely ordered array, is selection sort faster than insertion sort?

I think selection sort is faster because we have O(n^2) search and O(n) swap but in insertion sort we have O(n^2) swap and O(n^2) search.

Can anyone please tell me if I'm correct or not? Thanks

Upvotes: 2

Views: 2040

Answers (1)

Joseph James
Joseph James

Reputation: 168

I've done some benchmarking on this topic on my own Python implementations. It depends heavily on what type of input you have. I found that Insertion Sort is slightly faster (like 3%) for randomly ordered input, but Selection sort is much faster for reverse sorted input. I had always heard that Selection Sort is the faster of the two, but my own benchmarks on my implementations didn't reflect that.

Upvotes: 2

Related Questions