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?
This question is related to
algorithm
sorting
insertion-sort
selection-sort
The answer is
What they both have in common is that they both use a partition to differentiate between the sorted part of the array and the unsorted.
The difference is, that with selection sort you are guaranteed that sorted part of the array won't change when adding elements to the sorted partition.
The reason being, because selection searches for the minimum of the unsorted set and adds it right after the last element of the sorted set, thereby increasing the sorted set by 1.
Insertion on the other hand, only just cares about the next element that is encountered, which is the first element in the unsorted part of the array. It will take this element and simply fit it into its proper place in the sorted set.
Insertion sort will typically always be a better candidate for arrays that are only partially sorted because you are wasting operations to find the minimum.
Conclusion:
Selection sort incrementally adds an element to the end by finding the minimum element in the unsorted section.
Insertion sort propagates the first element found in the unsorted section into anywhere in the sorted section.
Both insertion sort and selection sort has an sorted list at the front, and unsorted list at the end, and what the algorithm does is also similar:
- Take an element from the unsorted list
- Put it into the sorted list
The difference is:
- Insertion sort take the first element of the unsorted list, and then do compare and swap in the sorted list to make sure the element goes to the right position, the effort is mostly in step #2 for insertion
auto insertion_sort(vector<int>& vs) { for(int i=1; i < vs.size(); ++i) { for(int j=i; j > 0; --j) { if(vs[j] < vs[j-1]) swap(vs[j], vs[j-1]); } } return vs; }
- Selection sort compare and mark the smallest element of the unsorted list, and then swap it with the first element of the unsorted list, actually include this element as part of the sorted list - the effort is mostly in step #1 for selection
auto selection_sort(vector<int>& vs) { for(int i = 0; i < vs.size(); ++i) { int iMin = i; for(int j=i; j < vs.size(); ++j) { if(vs[j] < vs[iMin]) iMin = j; } swap(vs[i], vs[iMin]); } return vs; }
The logic for both algorithms is quite similar. They both have a partially sorted sub-array in the beginning of the array. The only difference is how they search for the next element to be put in the sorted array.
Insertion sort: inserts the next element at the correct position;
Selection sort: selects the smallest element and exchange it with the current item;
Also, Insertion Sort is stable, as opposed to Selection Sort.
I implemented both in python, and it's worth noting how similar they are:
def insertion(data):
data_size = len(data)
current = 1
while current < data_size:
for i in range(current):
if data[current] < data[i]:
temp = data[i]
data[i] = data[current]
data[current] = temp
current += 1
return data
With a small change it is possible to make the Selection Sort algorithm.
def selection(data):
data_size = len(data)
current = 0
while current < data_size:
for i in range(current, data_size):
if data[i] < data[current]:
temp = data[i]
data[i] = data[current]
data[current] = temp
current += 1
return data
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;
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.
Insertion sort does a lot more swapping that selection. Here is an example:
The choice of these 2 sorting algorithms comes down to the data structure used.
When you are using arrays, use selection sort (although why, when you can use qsort?). When you are using linked lists, use insertion sort.
This is because:
- Linked list traversal is more expensive than arrays.
- Linked list insertion is far cheaper than arrays.
Insertion sort injects the new value into the middle of the sorted segment. Hence, data needs to be "pushed back". However, when you are using a linked list, by twisting 2 pointers, you have effectively pushed the entire list back. In an array, you must perform n - i swaps to push the values back, which can be very expensive.
Selection sort always appends to the end, so it doesn't have this problem when using arrays. Hence, data does not need to be "pushed back".
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.
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
selection -selecting a particular item(the lowest) and swap it with the i(no of iteration)th element. (i.e,first,second,third.......) hence,making the sorted list on one side.
insertion- comparing first with second compare third with second & first compare fourth with third,second & first......
Although Time Complexity of selection sort and insertion sort is the same, that is n(n - 1)/2. The average performance insertion sort is better. Tested on my i5 cpu with random 30000 integers, selection sort took 1.5s in average, while insertion sort take 0.6s in average.
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.
It's possible that the confusion is because you're comparing a description of sorting a linked list with a description of sorting an array. But I can't be sure, since you didn't cite your sources.
The easiest way to understand sorting algorithms is often to get a detailed description of the algorithm (not vague stuff like "this sort uses swap. Somewhere. I'm not saying where"), get some playing cards (5-10 should be enough for simple sort algorithms), and run the algorithm by hand.
Selection sort: scan through the unsorted data looking for the smallest remaining element, then swap it into the position immediately following the sorted data. Repeat until finished. If sorting a list, you don't need to swap the smallest element into position, you could instead remove the list node from its old position and insert it at the new.
Insertion sort: take the element immediately following the sorted data, scan through the sorted data to find the place to put it, and put it there. Repeat until finished.
Insertion sort can use swap during its "scan" phase, but doesn't have to and it's not the most efficient way unless you are sorting an array of a data type which: (a) cannot be moved, only copied or swapped; and (b) is more expensive to copy than to swap. If insertion sort does use swap, the way it works is that you simultaneously search for the place and put the new element there, by repeatedly swapping the new element with the element immediately before it, for as long as the element before it is bigger than it. Once you reach an element that isn't bigger, you've found the correct location and you move on to the next new element.
In layman terms, (and probably the easiest way to attain a high level understanding of the problem)
Bubble sort is similar to standing in a line and trying to sort yourselves by height. You keep switching with the person next to you until you are at the right place. This takes place all the way from the left (or right depending on the implementation) and you keep switching until everybody is sorted.
In selection sort, however, what you are doing is similar to arranging a hand of cards. You look at the cards, take the smallest one, place it all the way to the left, and so on.
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.
I want to add a little bit of improvement from an almost excellent answer from user @thyago stall above. In Python, we can do one line swapping. The selection_sort below also has been fixed by just swapping the current element with the minimum element at the right side.
In insertion sort we will run the outer loop from the second element and do an inner loop on the left side of the current element, shifting the smaller elements to the left.
def insertion_sort(arr):
i = 1
while i < len(arr):
for j in range(i):
if arr[i] < arr[j]:
arr[i], arr[j] = arr[j], arr[i]
i += 1
In selection sort, we also run the outer loop but instead of starting from the second element, we start from the first element. Then inner loop will loop the current + i element to the end of array to find the minimum element and we will swapped with the current index.
def selection_sort(arr):
i = 0
while i < len(arr):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
i += 1
Insertion sort do not swap things. Even though it make use of a temp variable, The point of making use of temp var is when we found a value at an index to be less compared to the value to its previous index, we shift the greater value to the place of lesser value's index which would over write things. Then we use the temp var to be substituted at the previous index. Example: 10, 20, 30, 50, 40. iteration 1: 10, 20, 30, 50, 50. [temp = 40] iteration 2: 10,20, 30, 40(temp's value), 50. So, we just insert a value at the desired position from some variable.
But When we consider selection sort, We first find the index having lower value and swap that value with the value from first index and keep on repeatedly swapping till all the indices get sorted. This is exactly same as traditional swapping of two numbers. Example: 30, 20 ,10, 40, 50. Iteration 1: 10, 20, 30, 40, 50. Here temp var is used exclusively for swapping.
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!
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
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.
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.
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:
- The inner loop will go through only half of its elements in an average case.
- The inner loop will be aborted even sooner if the array is almost sorted.
- 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.
Source: Stackoverflow.com