Section 26.6 Insertion Sort
In , we approach the problem of sorting a list by inserting one new item at a time into the sorted portion of the list.
Insertion sort also does \(n - 1\) passes to sort n items. It starts by assuming that the first item is already sorted. On each pass, it takes the next unsorted item and inserts it into the correct position within the sorted portion of the list by swapping it leftward until it is in the correct location.
Note that sometimes, the current value being inserted does not need to travel far. Other times, it may need to travel all the way to the front of the list. No matter how far it travels, it always does so by swapping leftward one position at a time.
Implemented to sort a vector in C++, it looks like this:
Some key details to notice:
-
The outer loop counts from 1 to n-1, representing the index of the element being inserted.
-
jin the inner loop represents where the item currently is. It starts at i and moves leftward. -
There are two conditions that might end the inner loop: 1) the item to the left of index
j(j - 1) is less than or equal to the current value; or 2)jreaches 0.
As with selection sort, we could do variations of this recipe:
-
We could start at the end of the list and work our way backwards through the list, to build the sorted portion from the end rather than the beginning.
-
We could sort in descending order rather than ascending order by changing the comparison in the inner loop from
<to>.
The worst case for insetion sort occurs when the list starts in reverse order. In that case, each item being inserted must travel all the way from its current position to index 0. In that case, the first item requires 1 comparison and swap, the second item requires 2 comparisons and swaps, and so on, up to \(n - 1\) comparisons and swaps for the last item. The total number of comparisons and swaps in the worst case is therefore:
\begin{equation*}
(n - 1) + (n - 2) + ... + 2 + 1
\end{equation*}
As with selection sort, that pattern can be simplified to \(O(n^2)\text{.}\) Thus, insertion sort has a time complexity of \(O(n^2)\) in the worst case.
However, if the list is already sorted, insertion sort is much more efficient. In that case, each item being inserted only requires one comparison (to see that it is already in the correct position) and no swaps. Thus, in the best case (an already sorted list), insertion sort does \(O(n)\) work.
You can see the adaptive behavior in the demonstration above. Use the Rest (Mostly Sorted) button to force the list into a mostly sorted state where just two items are out of order. The algorithm will not require many total steps to complete in this case.
Insertion sort is a stable algorithm as long as we use
< to compare elements. That way, if elements are “equal”, the item on the right will not insert itself past the item on the left. Consider the list {B(1), B(2), A}. When B(2) compares itself to B(1), it will not swap leftward since it is not less than B(1), preserving the relative order of the two B’s.
In the worst case (general case), insertion sort has a time complexity of \(O(n^2)\text{.}\)
Insertion sort is adaptive. It only involves \(O(n)\) work when the list is already sorted. (If a fixed number of items are out of order, it still does \(O(n)\) work.)
Insertion sort is stable.
Checkpoint 26.6.1.
We are doing an insertion sort on the vector
A, D, F, C, B. We are about to start the pass to insert C. Put the blocks in the correct order to show the state after that pass completes
Checkpoint 26.6.2.
Checkpoint 26.6.3.
Suppose you have the following vector of numbers to sort: [11, 7, 14, 12, 1, 19, 6, 18, 8, 20] which vector represents the partially sorted vector after three steps of insertion sort?
- [1, 6, 7, 11, 14, 12, 1, 19, 18, 8, 20]
- Insertion sort does not insert the smallest value. It inserts the next item in the unsorted portion of the list into the sorted portion.
- [1, 7, 11, 12, 14, 19, 6, 18, 8, 20]
- That went too far. The items that were at indexes 1-3 should have been inserted. Index 4 should not have been inserted yet.
- [7, 11, 14, 12, 1, 19, 6, 18, 8, 20]
- Three passes should result in the first four items being sorted. Three items were inserted and we started with one item sorted.
- [7, 11, 12, 14, 1, 19, 6, 18, 8, 20]
You have attempted of activities on this page.
