Selection sort vs. insertion sort

Let’s suppose that we are sorting a list of N elements. We have placed these numbers on a horizontal line. When we are done, each number will be greater than or equal to its neighbor on the left. The left-most number will be the smallest number and the right-most number will be the largest.

Both the selection sort algorithm and the insertion sort algorithm will produce this result in N steps.

At the k-th step, the first k elements of the list (the left part of the list) will be in order. The order of the remaining N – k elements (the right part of the list) is unknown.

In the selection sort, those first k elements will be the smallest elements in the list.

In the insertion sort, those k elements will be the k numbers that were first in the list before the sorting began.

At each step, the selection sort searches through the N – k still unsorted elements to find the smallest element in that part of the list. The algorithm moves that element to the end of the already sorted part of the list. At the end of this step, the first k + 1 elements of the list are in order and there are N – k – 1 yet to be sorted elements.

At each step, the insertion sort searches through the already k elements that are already in order to find the right spot in which to place the first element in the still unsorted part of the list. Again, at the end of this step, the first k + 1 elements of the list are in order and there are N – k – 1 yet to be sorted elements.

The selection sort must find at each step the smallest number in the still unsorted part of the list. To be sure that it has found the smallest number, it must examine each number. We will usually write code that searches left to right through the unsorted part of the list, but the direction of the search does not matter. What does matter is that the search goes all the way through the unsorted part of the list at every step.

The insertion sort must find the right spot at which it will be place the next number. It starts that search at the right end of the already sorted part of the list. The search could end right there. The next number might already be in the right place or it might belong somewhere in the middle of the already sorted part of the list. In either case, this algorithm does not need to examine every element in the already sorted part of the list.

At each step, the selection sort swaps numbers at two positions in the list. It swaps the smallest value in the unsorted part of the list with the first value in the unsorted part of the list.

At each step. the insertion sort may have to make a hole in the sorted part of the list into which it inserts the next value. To make a hole, it has to shuffle some numbers to the right.

Sometimes the computer does more work in executing an insertion sort on one list but less work on another list of the same length. How much work depends upon how well ordered the list was to start.

The computer does the same amount of work when it executes a selection sort on one list as it does when it executes the algorithm on any other list of the same length.