Insertion Sort
[Insertion Sort] [Hello. This is Rachel Cardell-Oliver from the University of Western Australia]
I'd like to show you insertion sort, an algorithm for taking a list of numbers and sorting them. An algorithm, remember, is simply a step-by-step procedure for accomplishing a task. The basic idea behind insertion sort, is to divide our list into two portions, a sorted portion and an unsorted portion.
At each step of the algorithm, a number is moved from the unsorted portion to the sorted portion until eventually the entire list is sorted. Here is the list of six unsorted numbers--3, 7, 4, 6, 8, and 5. Since these numbers are not all in ascending order, they're unsorted. Since we haven't started sorting yet, we'll consider all six elements our unsorted portion.
3, 7, 4, 6, 8, and 5
Once we start sorting, we'll put these sorted numbers to the left of these. So, let's start with 3, the first element in our list. We don't have any elements in our sorted portion yet, so let's simply consider 3 to be the start and end of our sorted portion. Now, our sorted portion has one number, 3, and our unsorted portion has these five numbers 7, 4, 6, 8, and 5.
Let's now insert the next number from our unsorted portion into the sorted portion.
To do so, we'll need to compare the 7 to the 3--the only element in our sorted portion so far. 7 is larger than 3, so we can simply append 7 to the end of the sorted portion of the list. Great! Now our sorted portion has two elements, and our unsorted portion has four elements. So, let's now move to the 4, the next element in the unsorted portion. So, where should this be placed in the sorted portion? \
Remember, we want to place this number in sorted order so our sorted portion remains correctly sorted at all times. If we place the 4 to the right of the 7, then our list will be out of order. So, let's continue moving right-to-left in our sort portion. As we move, let's shift each number down a place to make room for the new number. Okay, 4 is bigger than 3, so we place 4 here and we're done.
Next consider 6, the first element in the unsorted portion. 6 is less than 7, so 7 gets moved up. But 6 is greater than 4 so we can put 6 in to the empty space we've just made.
Next consider 8. Since 8 is greater than 7 it is already in the right place and there is no work to do. Finally consider 5. 5 is less than 8 so we move 8 up.
5 is also less than 7 so we move 7 up. 5 is also less than 6 so we move 6 up. Now 5 is greater than 4 so we can place 5 in the space we have made for it.
And we're done. We have no more elements in the unsorted portion, and our sorted portion is in the correct order. The numbers are ordered from smallest to largest.
[code]
Let's take a look at some Java code that describes the steps we just performed.
On line 15, we can see that we'll need to iterate over each element in the list except the first (that is index 0), since the first element in the unsorted portion will simply become the first element in the sorted portion. On lines 2 and 3, we're keeping track of our current place in the unsorted portion. key represents the number we are currently moving into the sorted portion, and i represents our index into the sorted portion.
On line 18, we're iterating back through the sorted portion from right to left. We want to stop iterating once the element to the left of our current position is less than the element we're trying to insert. On line 19, we're shifting each element we encounter one space to the right. That way, we'll have a clear space to insert into when we find the first element less than the element we're moving. On line 20, we're updating our counter to continue to move left through the sorted portion. Finally, on line 22, we're inserting the element into the sorted portion of the list.
We know that it's okay to insert into position i+1, because we've already moved the element that used to be there one space to the right. Remember, we're moving through the sorted portion from right to left, but we're moving through the unsorted portion from left to right.
All right. Let's now take a look at how long running that algorithm took. We'll first ask the question how long does it take for this algorithm to run in the worst case. Recall that we represent this running time with Big O notation. In order to sort our list, we had to iterate over the elements in the unsorted portion, and for each of those elements, potentially over all elements in the sorted portion. Intuitively, this sounds like an O(n^2) operation.
Looking at our Java code, we have a loop nested inside another loop, which, indeed, sounds like an O(n^2) operation. However, the sorted portion of list didn't contain the entire list until the very end. Still, we could potentially insert a new element at the very beginning of the sorted portion on every iteration of the algorithm, which means that we'd have to look at each element currently in the sorted portion. So, that means we could potentially make one comparison for the second element, two comparisons for the third element, and so on. So, the total number of steps is the sum of the integers from 1 to the length of the list minus 1. We can represent this with a summation.
We won't go into summations here, but it turns out that this summation is equal to n (n - 1) over 2, which is equivalent n^2/2 - n/2. When talking about asymptotic runtime, this n^2 term is going to dominate this n term. So, insertion sort is Big O n squared.
What if we ran insertion sort on an already sorted list. In that case, we'd simply build up the sorted portion from left to right. So, we'll only need n steps. That means that insertion sort has a BEST-CASE performance of n, which we represent with Ω(n).
And that's it for insertion sort, just one of the many algorithms we can use to sort a list.
[ This talk is based on a video by Tommy MacWilliam for Harvard University CS50.TV]