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

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

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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