algorithm - Insertion Sort vs. Selection Sort - Stack Overflow

Excerpt

I am trying to understand the differences between Insertion Sort and Selection Sort. They both seem to have two components: an unsorted sub-list and a sorted sub-list. They both seem to take one el…

---

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

answered Apr 3, 2013 at 22:07

[

](https://stackoverflow.com/users/1862812/nikolay-kostov)

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.

answered Apr 3, 2013 at 22:42

[

](https://stackoverflow.com/users/210211/comingstorm)

comingstorm

26k3 gold badges44 silver badges67 bronze badges

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.

answered Oct 2, 2018 at 15:06

[

](https://stackoverflow.com/users/10154009/akash-sharma)

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.

answered Apr 3, 2013 at 22:55

[

](https://stackoverflow.com/users/13005/steve-jessop)

Steve Jessop

278k40 gold badges467 silver badges706 bronze badges

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

answered Dec 27, 2015 at 17:55

[

](https://stackoverflow.com/users/4619812/thyago-stall)

thyago stall

1,7043 gold badges17 silver badges30 bronze badges

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.

answered Jul 21, 2017 at 16:36

[

](https://stackoverflow.com/users/1162620/ravi)

Ravi

31.2k43 gold badges122 silver badges178 bronze badges

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”.

answered Aug 5, 2020 at 18:26

[

](https://stackoverflow.com/users/2646772/john)

John

8186 silver badges11 bronze badges

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

answered Dec 25, 2015 at 18:52

[

](https://stackoverflow.com/users/3323163/my-an-lien)

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!

answered Sep 27, 2014 at 21:57

[

](https://stackoverflow.com/users/4087015/muath)

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.

answered Feb 12, 2015 at 2:08

[

](https://stackoverflow.com/users/1037407/ecir-hana)

Ecir Hana

11.3k13 gold badges71 silver badges124 bronze badges

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.

answered May 27, 2015 at 13:47

[

](https://stackoverflow.com/users/3354993/mankadnandan)

mankadnandan

1,0331 gold badge8 silver badges11 bronze badges

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.

answered Nov 27, 2018 at 17:04

[

](https://stackoverflow.com/users/2872878/danila-piatov)

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.

answered Aug 5, 2020 at 17:36

[

](https://stackoverflow.com/users/14055601/like)

Like

1411 silver badge2 bronze badges

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;

answered Dec 2, 2016 at 14:38

[

](https://stackoverflow.com/users/5095067/pankti)

Pankti

4214 silver badges13 bronze badges

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:

1. Take an element from the unsorted list
2. 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;
}

answered Nov 28, 2020 at 13:55

[

](https://stackoverflow.com/users/70198/baiyan-huang)

Baiyan Huang

6,7038 gold badges48 silver badges74 bronze badges

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

answered Feb 7, 2021 at 8:50

[

](https://stackoverflow.com/users/946199/jon-kartago-lamida)

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

answered Sep 22, 2019 at 16:51

[

](https://stackoverflow.com/users/4617883/user4617883)

user4617883

1,4571 gold badge13 silver badges23 bronze badges

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.

answered Jun 19, 2019 at 14:37

[

](https://stackoverflow.com/users/518346/sid)

Sid

3492 silver badges12 bronze badges

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.

answered Jul 8, 2019 at 11:20

[

](https://stackoverflow.com/users/11754045/aravindkumar-chilakamarri)

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.

answered Mar 26, 2020 at 22:01

[

](https://stackoverflow.com/users/5162155/abc)

abc

1,97517 silver badges31 bronze badges

Similarities between Insertion Sort and Selection Sort?

1. Both algorithms divide the list into 2 conceptual lists, one which is sorted and another which is unsorted.

---

2. In both insertion sort and Selection sort, after N^th iteration, you will have N elements sorted.

---

3. Insertion sort: You start with the first element at first iteration, then on next iteration you pick the next element and swap the first and the second element (if unsorted). After each iteration, you pick another next element and sort with the conceptual list again, trying to expand the sorted conceptual list and shrink the unsorted conceptual list.

   Selection sort: You start with finding the smallest element in the list and swap the first element with that smallest element. On the next iteration, you search the 2^nd smallest element and swap that with 2^nd element in the list. And continue so on until you reach the end!

   Insertion Sort Graphically:

   

   Selection Sort Graphically:

   

Differences between Insertion Sort and Selection Sort?

1. Insertion Sort has time complexity of O(n^2) and Ω(n).

   Selection sort has time complexity of O(n^2) and Ω(n^2).

---

2. Insertion sort is stable.

   Selection sort is unstable.

_{Wikipedia Definition: Stable sort algorithms sort equal elements in the same order that they appear in the input.}

---

3. Insertion Sort is slightly better than the Selection sort because it internally uses reference of locality to find the next element. Also, through caching, it achieves slight performance benefits.

---

4. Insertion sort is a bit more efficient and easier to implement with linked lists due to its natural ability to insert elements without requiring extensive pointer manipulations

---

5. Insertion can be used on small data structures. For larger data structures, insertion sort is not recommended due to quadratic average performance.

   Similarly, Selection sort’s worst performance is similar to bubble sort, and it should not be used for sorting larger datasets.

answered Aug 26, 2023 at 15:02

[

](https://stackoverflow.com/users/6073148/zahid-khan)

Zahid Khan

2,8282 gold badges25 silver badges34 bronze badges

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…

a link where all sortings are compared

answered Apr 24, 2018 at 15:33

[

](https://stackoverflow.com/users/2606228/nikhil2000)

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.

answered Feb 1, 2017 at 19:00

[

](https://stackoverflow.com/users/7480482/haxgad)

haxgad

3974 silver badges9 bronze badges