Selection Sort on 1 Million Elements: Is It Feasible?

[rsala004]

if you have an array with size 1000000, would selection sort be feasible on a everyday laptop computer, or just too large?

I imagine it would take (1Million)²/2 loops to complete the sort

 

[tnutty]

No, use your standard library sorting algo or google sorting and you will find many better ones, like quicksort, for example.

 

[rcgldr]

I think what's he's asking is how long would it take to execute a small loop 1 trillion times on a modern lap top.

From wiki

http://en.wikipedia.org/wiki/Instructions_per_second

Probably between 10 and 20 billion instructions per second, so 50 to 100 seconds per trillion instructions, assuming the condiitions mentioned in the wiki article. So ballpark about 100 seconds per instruction in that selective sort loop. This is a crude estimate, it could be 1000 seconds per trillion instructions when you take memory accesses into account.

Here's a link to a prior thread about sorting which includes some links to source code of various sort programs:

https://www.physicsforums.com/showthread.php?t=218369