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?

Solution 1

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

Solution 2

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.

Solution 3

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.

Solution 4

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.

Solution 5

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

View more solutions

Comments

[eb80]

@Nikolay - This is just copied from cheetahonfire.blogspot.com/2009/05/… which I already read. Is there anything more concerte as I have read conflicting articles.

[Nikolay Kostov]

The main difference is the selection step. The selection sort selects the smallest one and swaps it with the first one The insertion sort inserts the current one in its appropriate position

[G. Bach]

@eb80 I'm not sure what material you're reading, but I don't see how an example could be more concrete than this?

[eb80]

This is very helpful... The last paragraph gets to the confusion I was having, which stemmed from variants on each sort.

[Jason Goemaat]

But what about the number of swaps? Selection always does n(n-1)/2 comparisons, but in the worst case it will only ever do n-1 swaps. In the worst case Insertion will do n(n-1)/2 comparisons as well as n(n-1)/2 swaps.

[human.js]

@eb80 please vote this as the answer . i can't see to find a better answer than this.

[XuDing]

He is asking about the difference between Selection and Insertion sort though

[Gavin Achtemeier]

+1 for noting that using insertion sort on a linked list is a completely different swap efficiency than with an in-place array

[Adorn]

worth noting, both are divide and conquer algorithms.

[Asky McAskface]

@Adorn Neither of these are divide and conquer algorithms.

[Adorn]

@AskyMcAskface, sure they are. I hope you are not stuck with the conceptual hurdle that divide and conquer has to divide a problem in a certain way, for example in half. Do you see it now? If not, try proving they are not fitting into the category, you will arrive at a conclusion that they actually do fit. It would be a different argument to say they are not good divide and conquer algorithms though..

[Asky McAskface]

@Adorn if you consider repeatedly selecting an element to be 'dividing' and finding it's correct position (and the other way around for insertion sort) to be 'conquering' then perhaps you can call these algorithms divide and conquer. However, in most computer science literatture you will find, as a rule of thumb, that divide and conquer algorithms are algorithms that are, by definition, recursive by nature. Note that I say by nature- iterative algorithms can be implemented with tail recursion and recursive algorithmds can be implemented iteratively with a stack.

[Adorn]

@AskyMcAskface, which book says so? CLRS gives a generic definition of divide and conquer, which satisfies the premise of selection and insertion sort. I am genuinely interested in finding a legitimate source. What you say is a generic understanding of what should be considered divide and conquer, but the definition should not have to do anything with the recursions per say

[Asky McAskface]

@Adorn CLRS explicitly states that divide and conquer alhorithms are recursive by nature! "Recall that in divide-and-conquer, we solve a problem recur- sively", boom, right off the bat on the chapter.

[Adorn]

@AskyMcAskface, I do not find the need of the further argument, as there is absolutely zero value addition to the discussion. I re-read section 2.3, and it still satisfies the paradigm, IMO. For others who are reading this, make sure you pay close attention to the "Paradigm", what "recursion" means in the context of a discussion, recurrences, and finally mixing the theory and practice. Solving few recurrences and proving the correctness of algorithms would definitely help

[Asky McAskface]

@Adorn The backfire effect

[Adorn]

@AskyMcAskface, lol, enjoy! In case you improve on a willingness to look at the things from a different perspective, you are welcome on a personal chat. but you have to promise the logical arguments there. Also, add the section where you found the quoted content in CLRS, let others know.

[JaydeepW]

Just check out mycodeschool on Youtube. However, this answer compliments what's explained in the videos of 2 algorithms on youtube.

[R Claven]

great answer. Thank you!

[Tony Ma]

sorry, I was wondering why (selection sort algorithm), the data[i] is exchanged with data[current] whenever data[i] is smaller. In the basic/original(?) selection sort, we find the minimum value among range(i, data_size) and exchange data[i] with that minimum value...that's a little different...

[Maxim Sagaydachny]

Welcome to the StackOverflow and thank you for the answer. Most likely you can see that many people have already contributed nice answers with visual illustrations. For example Nikolay Kostov 7 years ago stated that time complexity are the same only in worst case for insertion sort. If you think he is wrong we welcome you to expand your answer with more details.

[Daniel]

@Gavin correct me if I'm wrong, but it seems to me insertionsirt would be better in something like linked lists but selection sort is actually more efficient than insertion sort with arrays. That's because you can't just 'insert' a value before another a value in an array. If you insert at index n in the sorted list, you have to shift over by one position all elements to the right. That means a read and write operation for each of those elements. With linked lists though you can actually just do an insertion.

[Daniel]

By point is that with arrays, common sense would say that insertion sort would perform stressed, not better than selection sort, especially since vietnamese swaps (reads, writes) are slower than comparisons

[Jon Kartago Lamida]

Yes, while the above selection method works, we can reduce non-necessary swap by just swapping once we found the minimum value on the right side of the array.