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

User · Answer

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;

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  lt  data size          for i in range current               if data current   lt  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  lt  data size          for i in range current  data size               if data i   lt  data current                   temp   data i                  data i    data current                  data current    temp          current    1      return data

User · Answer

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

User · Answer

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

User · Answer

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  lt  len arr           for j in range i               if arr i   lt  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  lt  len arr           min idx   i         for j in range i   1  len arr                if arr min idx   gt  arr j                   min idx   j         arr i   arr min idx    arr min idx   arr i      i    1

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  amp  first            compare   fourth with third second  amp  first        a link where all sortings are compared

User · Answer

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  quot pushed back quot    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  quot pushed back quot

User · Answer

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 lt int gt  amp  vs      for int i 1  i  lt  vs size      i          for int j i  j  gt  0  --j              if vs j   lt  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 lt int gt  amp  vs      for int i   0  i  lt  vs size      i          int iMin   i      for int j i  j  lt  vs size      j              if vs j   lt  vs iMin   iMin   j            swap vs i   vs iMin          return vs

User · Answer

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

User · Answer

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

User · Answer

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

[algorithm] Insertion Sort vs. Selection Sort

Examples related to algorithm

Examples related to sorting

Examples related to insertion-sort

Examples related to selection-sort