Difference between insertion and selection sort?

Answer 1

Before we examine the differences, let us examine the implementations. The code that follows is written in C++, but can be easily adapted to other languages.

Firstly, let us assume we have an array of num elements (we'll use integers here, but typically you will use pointers to maintain efficiency):

int array[num];

A selection sort has the following nested loop structure:

for( int outer=0; outer < num-1; ++outer )

{

int min = outer;

for( inner=outer+1; inner < num; ++inner )

{

if( array[inner] < array[min] )

min = inner;

}

if( min != outer )

swap( array[min], array[outer] );

}

Whereas an insertion sort has the following nested loop structure:

for( index=1; index < num; ++index )

{

value = array[index];

hole = index;

while( hole > 0 && value < array[hole-1] )

array[hole] = array[--hole];

array[hole] = value;

}

Although both algorithms split an array into two subsets (a sorted subset to the left and an unsorted subset to the right) and both move one element from one set to the other on each iteration of the outer loop, the selection sort begins with an empty sorted subset while the insertion sort begins with a sorted subset of one element (any array with only one element can always be regarded as being sorted).

In both cases, the outer loop keeps track of the initial index of the current unsorted subset and both perform a complete traversal of the unsorted subset. However selection sort stops when there is only one unsorted element left, which automatically becomes the largest value in the sorted set and therefore doesn't need to move, whereas insertion sort traverses the entire unsorted subset.

The key difference is in the inner loops. With selection sort, the inner loop skips the first unsorted element and traverses the remainder of the unsorted subset locating the index of the lowest value (recorded by min). At the end of the inner traversal, if min is not the same as the outer loop index then the values are swapped. Thus the sorted subset gains a new element containing the next largest value on each iteration, beginning with the lowest value.

With insertion sort, the outer loop extracts the first unsorted element's value and stores its index (hole). There isn't really a hole in the array, it's simply a marker to determine where the extracted value will be inserted. The inner while loop then traverses the sorted subset. On each iteration, if the hole marker is non-zero and the value is less than the value of the element to the left of the hole marker, then that element's value is copied into the hole to its right and the hole marker moves left. When the inner loop ends, the hole marker denotes where the extracted value should be placed. Thus if the extracted value is greater than or equal to the largest sorted value, then the value doesn't move (it was already sorted), otherwise it is inserted into its correct position within the sorted subset.

It can be proved that although selection sort only requires one swap at most for every iteration of the outer loop, it must perform (num-1)! comparisons in total (that is, for num=6 there are 5+4+3+2+1 comparisons in total). It should be noted that every swap incurs three copy processes, however a single copy takes less time than a single comparison.

By contrast, insertion sort stops comparing when the insert point is located, thus, on average, there will be fewer comparisons than (num-1)!. However, while every iteration of the outer loop incurs two copy processes even if the current element doesn't need to move, and additional copy processes for each movement of the hole marker, it's wrong to assume selection sort is always faster. On average, it is actually slower.

Looking at the worst case example, let us suppose the array is in reverse order. Selection sort requires (num-1)! comparisons no matter what and will also incur n-1 swaps in total (which is 3(num-1) copies in total). By contrast, insertion sort also requires (num-1)! comparisons but requires 2(num-1)+(num-1)! copy processes. The end result is that selection sort performs slightly better, and will improve as the array size increases.

Another worst case example is the already-sorted array. Again, selection sort requires (num-1)! comparisons but no swaps at all. However, insertion sort only requires num-1 comparisons and 2(num-1) copies. In this case, insertion sort performs slightly better, and will improve as the array size increases.

While both algorithms are fairly efficient when dealing with small arrays (typically up to 20 elements), with insertion sort performing better on average, they are highly inefficient when dealing with larger arrays. For this you need recursive, logarithmic, divide-and-conquer algorithms, such as quicksort, which are capable of sorting num elements with only (log num) comparisons. However, these algorithms don't perform well with smaller subsets, so it pays to combine the two into a hybrid algorithm. That is, when a logarithmic algorithm reduces a subset to 20 elements or less, then that subset can be sorted far more efficiently with an insertion sort.

Answer 2

what is the difference between selection sort and insertion sort?