Insertion Sort vs. Selection Sort

Question

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

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.

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.

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.