Description
Insertion sort is a sort-as-you-go method. You sort the elements are you walk through them. You “insert” the element into an already sorted list. This method is more complex to code. Click here for the Insertion Sort assignment.
Logic
- Basic Logic
- Choose an element to sort.
- Assume all of the elements left of the element you are going to sort are already sorted.
- Find where in the array to the left the element goes, place it there, and move all the other items to the right.
- Repeat with the next element in the array.
- Walkthrough Logic
- Start with the second element in the array since the first element is already sorted with itself.
- Compare the second element with the first element. If the second element is smaller (ascending order) than the first, swap the elements.
- Look at the third element.
- Compare it with the second. If it goes before the second, then compare it with the first to determine where it should fit.
- Move the third element into the location where it should go and then move the other elements over.
- Repeat
Coding
- You will need two loops for this, but the inner loop will be different.
- Outer loop
- controls which element is being sorted.
- starts at the second element because the first is sorted with itself.
- needs to go to the last element because this algorithm is looking left, not right.
- Inner loop
- this loops sorts the element chosen in the outer loop with all the elements to the left
- a while or do-while works better for this loop
- keep looking left until you find an element that is smaller than the element to be sorted. Don’t go past zero.
- The sorted element goes to the right (+1) of the element smaller or at position 0 if it is the smallest.
- The shifting of items around can be done one of two ways,
- Bubble sort the element to be sorted back to the left until it is where it needs to be.
- Place the element to be sorted where it needs to be and run a for loop to shift everything to the right.
Example
- Initial array (10 elements): 31, 45, 13, 38, 52, 20, 98, 8, 78, 62
- First pass
- Look at 45.
- Compare 31.
- Since 31 < 45, you do nothing.
- Array after first pass: 31, 45, 13, 38, 52, 20, 98, 8, 78, 62
- Second pass
- look at 13
- 13 < 45 && 13 < 31
- 13 gets moved to the first spot, 31 to the second, 45 to the third spot.
- Array after second pass 13, 31, 45, 38, 52, 20, 98, 8, 78, 62
- Third pass
- look at 38
- 38 < 45 but 38 > 31. Stop there. I don’t need to compare 38 with 13 since the elements to the left are already sorted.
- Put 38 in the 3rd spot and move 45 to the 4th spot
- Array after third pass 13, 31, 38, 48, 52, 20, 98, 8, 78, 62
- Repeat until finished with 62.
Advantages and Disadvantages
- More complex to code than Bubble or Selection Sort, but not as complicated as Merge Sort.
- Very efficient at inserting a single element into an already sorted list.
- Not that efficient at sorting large lists because of the constant swapping and moving elements.
Other Resources
Edhesive T2 Lesson 16: Insertion Sort
AP College Board Video: Insertion Sort
Geeks for Geeks: text explanation