There are lots of different sorting algorithms and we will explore several of them in this unit. Today we will be talking about insertion sort. The concept of insertion sort is very simple. Begin by dividing the list into two partitions, a sorted partition and an unsorted partition. Now these partitions are imaginary, there's not really any division going on between them, we're just drawing an imaginary line between the part of the list that is sorted and the part of the list that is unsorted.
At the beginning of each iteration, the leftmost element in the unsorted partition is moved to the rightmost position in the sorted partition. If the new element is out of place, it is shifted to the left until it is in place. Repeat until the sorted partition is the entire list. Begin by dividing the list into sorted and unsorted partitions. At first, the sorted partition has only one element.
In this case, 84 is the only element in the sorted partition of the list. The remaining three elements are unsorted. With each iteration, we move the leftmost element in the unsorted partition to the rightmost position in the sorted partition.
Again, this is just moving the imaginary line between the green elements and the gray elements so that it includes 79. Sometimes the new element needs to be swapped one or more times to its left. In this case, 79 is less than 84, so we have to swap those two values to maintain the sorted nature of the sorted partition. Sometimes no swap is needed at all.
This time, when we add 86 to the sorted partition, it is already greater than the value to its left, 84, and so it does not need to swap. Other times, we may need to swap the value. all the way to its left. In this case, 70, which we've just added to the sorted partition, is now the smallest element in the sorted partition, and so it has to shift all the way to the left. Once we are finished, though, there are no elements remaining in the unsorted partition, and so the sort is finished.
Let's take a closer look at how insertion sort works. Insertion sort begins by dividing the list into sorted and unsorted partitions. This is really just an imaginary line that separates the two partitions.
Here we are also using color, with green representing the elements in the sorted partition and gray representing the elements in the unsorted partition. With each iteration, Insertion Sort moves the imaginary line one index to its right. In the best case scenario, the new element doesn't need to be moved into place.
In this example, 5 is already greater than 2, and so we do not need to move 5. Sometimes the element needs to be shifted one or more indices to its left. In this case, 4 is less than 5 and so it needs to be moved to the left. This is what we do to keep the sorted partition sorted.
In the worst case scenario, the new element needs to be shifted all the way to the left. In this case, because 1 is the smallest element in the entire list, when we add it to the sorted partition, it needs to move all the way to index 0. Insertion sort is implemented with two loops. One loop iterates through the indices in the list one at a time, adding elements from the unsorted partition into the sorted partition.
A second loop is used to shift each element to its left as needed. The performance of insertion sort changes dramatically depending on the configuration of the input. The algorithm must iterate over the entire list.
Remember, we iterate index by index Bringing one element from the unsorted partition into the sorted partition with each iteration This is an O of n or linear time operation each time an element is added to the sorted partition It must be shifted zero or more times to its left Depending on whether or not it is less than the value to its left if the input is sorted then insertion sort doesn't need to Shift any elements at all. This is because each time we add a new element to the sorted partition, it is already in the right place and therefore does not need to be shifted. This means that the best case time complexity is O of n or linear time. That's because we are iterating through all of the indices in the list, but we never have to perform a shift.
This also means that mostly sorted data will be very close to O of n or linear time as well. If the input is random, then each element has to be shifted an average of about one half the number of elements in the sorted partition. This is an O of one half n operation.
The O of one half n operation needs to be done once for each of the n elements in the list. Therefore, the average complexity is O of one half n times n, or, because we don't care about scalars as n approaches infinity, just O of n squared, or quadratic time. If the input is in reverse order, then every element must be shifted all the way to its left.
Each time we add a new element to the sorted partition, it is now the smallest element in the sorted partition and therefore has to be shifted all the way to the left. Like the average case, this worst case is expected to be O of n squared. Insertion sort runs in quadratic time in the average and worst cases.
The time complexity grows much more quickly than the size of the input. However, if data is sorted or nearly sorted, insertion sort performs quite well. This makes it very useful under certain conditions.