is selection sort faster than insertion for big arrays?
Possible Duplicate:
Efficency of Insertion Sort vs Bubble sort vs Selection sort?
is selection sort faster than insertion for big arrays? When its in the worstest case?
I know insertion be faster than selection, but for large arrays and in the worstest case?
Answer
The size of the array involved is rarely of much consequence.
The real question is the speed of comparison vs. copying. The time a selection sort will win is when a comparison is a lot faster than copying. Just for example, let's assume two fields: a single int as a key, and another megabyte of data attached to it.
In such a case, comparisons involve only that single int, so it's really fast, but copying involves the entire megabyte, so it's almost certainly quite a bit slower.
Since the selection sort does a lot of comparisons, but relatively few copies, this sort of situation will favor it. The insertion sort does a lot more copies, so in a situation like this, the slower copies will slow it down quite a bit.
As far as worst case for a selection sort, it'll be pretty much the opposite -- anything where copying is fast, but comparison is slow.