is selection sort faster than insertion for big arrays?

Question

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?

Solution 1

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.

Solution 2

According to the Wikipedia article,

In general, insertion sort will write to the array O(n2) times, whereas selection sort will write only O(n) times. For this reason selection sort may be preferable in cases where writing to memory is significantly more expensive than reading, such as with EEPROM or flash memory.

That's going to be true regardless of the array size. In fact, the difference will be more pronounced as the arrays get larger.