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

Both algorithms generally works like this

Step 1: take the next unsorted element from the unsorted list then

Step 2: put it in the right place in the sorted list.

One of the steps is easier for one algorithm and vice versa.

Insertion sort: We take the first element of the unsorted list, put it in the sorted list, somewhere. We know where to take the next element (the first position in the unsorted list), but it requires some work to find where to put it (somewhere). Step 1 is easy.

Selection sort: We take the element somewhere from the unsorted list, then put it in the last position of the sorted list. We need to find the next element (it most likely is not in the first position of the unsorted list, but rather, somewhere) then put it right at the end of the sorted list. Step 2 is easy

Answer 2

SELECTION SORT
Assume that there is array of numbers written in a particular/random fashion and lets say we are to arrange in increasing order..so, take one number at a time and replace them with the smallest no. available in the list. by doing this step we'll ultimately get our desired result.

INSERTION SORT
Keeping the similar assumption in mind but the only difference is that this time we are selecting one number at a time and inserting it in the presorted part, that reduced the comparisons and hence is more efficient.

Answer 3

Both insertion sort and selection sort have an outer loop (over every index), and an inner loop (over a subset of indices). Each pass of the inner loop expands the sorted region by one element, at the expense of the unsorted region, until it runs out of unsorted elements.

The difference is in what the inner loop does:

• In selection sort, the inner loop is over the unsorted elements. Each pass selects one element, and moves it to its final location (at the current end of the sorted region).

• In insertion sort, each pass of the inner loop iterates over the sorted elements. Sorted elements are displaced until the loop finds the correct place to insert the next unsorted element.

So, in a selection sort, sorted elements are found in output order, and stay put once they are found. Conversely, in an insertion sort, the unsorted elements stay put until consumed in input order, while elements of the sorted region keep getting moved around.

As far as swapping is concerned: selection sort does one swap per pass of the inner loop. Insertion sort typically saves the element to be inserted as temp before the inner loop, leaving room for the inner loop to shift sorted elements up by one, then copies temp to the insertion point afterwards.

Answer 4

I'll give it yet another try: consider what happens in the lucky case of almost sorted array.

While sorting, the array can be thought of as having two parts: left hand side - sorted, right hand side - unsorted.

Insertion sort - pick first unsorted element and try to find a place for it among the already sorted part. Since you search from right to left it might very well happen that the first sorted element you are comparing to (the largest one, most right in the left part) is smaller than the picked element so you can immediately continue with the next unsorted element.

Selection sort - pick the first unsorted element and try to find the smallest element of the whole unsorted part, and exchange those two if desirable. The problem is, since the right part is unsorted, you have to go thought every element every time, since you cannot possibly be sure whether there is or is not even smaller element than the picked one.

Btw., this is exactly what heapsort improves upon selection sort - it is able to find the smallest element much more quickly because of the heap.

Answer 5

A simple explanation could be as below:

Given: An unsorted array or list of numbers.

Problem Statement: To sort the list/array of numbers in ascending order to understand the difference between Selection Sort and Insertion Sort.

Insertion Sort: You see the list from top to bottom for easier understanding. We consider the first element as our initial minimum value. Now, the idea is that we traverse across each index of that list/array linearly to find out if there is any other element at any index that is having a lesser value than the initial minimum value. If we find such a value, we just swap the values at their indexes, i.e. lets say 15 was the minimum initial value at index 1 and during linear traversal of the indexes, we come across a number with lesser value, say 7 at index 9. Now, this value 7 at index 9 is swapped with the index 1 having 15 as its value. This traversal will continue to do comparison with the value of the current index with the remaining indexes to swap for the smaller value. This continues till the second last index of the list/array, as the last index is already sorted and doesn't have a value to check with outside the array/list.

Selection Sort: Let's assume that the first index element of the list/array is sorted. Now from the element at second index, we compare it with its previous index to see if the value is smaller. The traversal could be visualized into two parts, sorted and unsorted. One would be visualizing a comparison check from the unsorted towards the sorted for a given index in the list/array. Let's say you have value 19 at index 1 and value 10 at index 3. We consider traversal from the unsorted to the sorted, i.e. right to left. So, lets say we have to sort at index 3. We see that it has a lesser value than index 1 when we compared from right to left. Once identified, we just place this number 10 of index 3 in the place of index 1 having value 19. The original value 19 at index 1 gets shifted by one place to the right. This traversal keeps on continuing for every element in the list/array till the last element.

I haven't added any code as the question seems about understanding the concept of the method of traversal.

Answer 6

Insertion sort does a lot more swapping that selection. Here is an example: