Insertion Sort vs. Selection Sort

Question

I am trying to understand the differences between Insertion Sort and Selection Sort.

They both seem to have two components: an unsorted list and a sorted list. They both seem to take one element from the unsorted list and put it into the sorted list at the proper place. I have seen some sites/books saying that selection sort does this by swapping one at a time while insertion sort simply finds the right spot and inserts it. However, I have seen other articles say something, saying that insertion sort also swaps. Consequently, I am confused. Is there any canonical source?

Answer 1

The inner loop of the insertion sort goes through already sorted elements (contrary to the selection sort). This allows it to abort the inner loop when the right position is found. Which means, that:

1. The inner loop will go through only half of its elements in an average case.
2. The inner loop will be aborted even sooner if the array is almost sorted.
3. The inner loop will abort immediately if the array is already sorted, making the complexity of the insertion sort linear in this case.

The selection sort will have to always go through all inner loop elements. That’s why the insertion sort is mostly preferred to the selection sort. But, on the other hand, the selection sort does much less element swaps, which might be more important in some cases.

Answer 2

In a nutshell, I think that the selection sort searches for the smallest value in the array first, and then does the swap whereas the insertion sort takes a value and compares it to each value left to it (behind it). If the value is smaller, it swaps. Then, the same value is compared again and if it is smaller to the one behind it, it swaps again. I hope that makes sense!

Answer 3

Selection Sort:

Given a list, take the current element and exchange it with the smallest element on the right hand side of the current element.

Insertion Sort:

Given a list, take the current element and insert it at the appropriate position of the list, adjusting the list every time you insert. It is similar to arranging the cards in a Card game.

Time Complexity of selection sort is always n(n - 1)/2, whereas insertion sort has better time complexity as its worst case complexity is n(n - 1)/2. Generally it will take lesser or equal comparisons then n(n - 1)/2.

Source: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

Answer 4

Selection Sort: As you start building the sorted sublist, the algorithm ensures that the sorted sublist is always completely sorted, not only in terms of it's own elements but also in terms of the complete array i.e. both sorted and unsorted sublist. Thus the new smallest element once found from the unsorted sublist would just be appended at the end of the sorted sublist.

Insertion Sort: The algorithm again divide the array into two part, but here the element is picked from second part and inserted at correct position to the first part. This never guarantees that the first part is sorted in terms of the complete array, though ofcourse in the final pass every element is at its correct sorted position.

Answer 5

In short,

Selection sort : Select the first element from unsorted array and compare it with remaining unsorted elements. It is similar to Bubble sort, but instead of swapping each smaller elements, keeps the smallest element index updated and swap it at the end of each loop.

Insertion sort : It is opposite to Selection sort where it picks first element from unsorted sub-array and compare it with sorted sub-array and insert the smallest element where found and shift all the sorted elements from its right to the first unsorted element.

Answer 6

Basically insertion sort works by comparing two elements at a time and selection sort selects the minimum element from the whole array and sorts it.

Conceptually insertion sort keeps on sorting the sub list by comparing two elements till the whole array is sorted while the selection sort selects the minimum element and swaps it to the first position second minimum element to the second position and so on.

Insertion sort can be shown as :

    for(i=1;i<n;i++)
        for(j=i;j>0;j--)
            if(arr[j]<arr[j-1])
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

Selection sort can be shown as :

    for(i=0;i<n;i++)
        min=i;
        for(j=i+1;j<n;j++)
        if(arr[j]<arr[min])
        min=j;
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;