Selection:
Two lists are maintained, a sorted and an unsorted list. Initially, the sorted list has 0 items in it, and the unsorted list has all the items in it. A linear search is then conducted in the unsorted list, and the highest/lowest value is found (depending on whether you are doing descending/ascending sort).
This item is then placed at the beginning of the unsorted list, and this item is now in order. So the sorted list size increases by one after each pass, and the unsorted list size decreases by one.
A linear search, then swap process is continued until all items are in order.
Insertion:
Two lists are maintained again.
The first item in the unsorted list is taken as being in order. The next item in the unsorted list is then looked at, and it is placed in its correct position in the sorted list. This is done by shuffling all the other items either up/down one place, and inserting the next item into the gap created.
After each pass, the sorted list size increases by one, the unsorted decreases by one.
Some comparisons:
As selection sort has a MUCH larger number of swaps (swaps take more processing power than a shuffle), this method is slower than an insertion sort FOR LARGE LISTS of data. The difference is so small for small lists that the overhead created by using the additional loops required takes more processing power than implementing a simple bubble sort.
But for large lists, the difference is about 66% less time taken with insertion sort (depending on the type of insertion sort used) than with a selection.
For the SDD syllabus - you DONT need to know the different types of insertion sorts. However, you need to associate Insertion with SHUFFLING.
Have a look at this program: Generate a list of data, and slow down the sorting process so you can actually see what is happening: (its only a 25kb zip file - so check it out! - its well worth it.)
http://www.fosweb.com/files/sort.zip
