Insertion sort is simply a method of putting a group of items that are out of order into the correct order. Imagine there are a group of people standing in a line in front of you. Then imagine you are tasked with putting them in height order. You'd probably be able to get the job done without any sort of method, and that's because you have a smart human brain. Computers, on the other hand, need very specific step-by-step instructions telling them exactly how to get the job done (AKA code). The procedures to solve one particular task are also often called algorithms. Basically, you can't give a computer a list of the people with their heights and tell it to "figure it out". You need to give it an algorithm to follow. This is where insertion sort comes in - it's one of the many sorting algorithms.
Consider the list of numbers above. We're going to put the numbers in ascending order using insertion sort. The first task is to look at the first number and put it in sorted order with all of the other numbers to the left of it. And since there are no numbers to the left, there's nothing to do. That was easy!
Okay, then we look one number to the right, and put that one in sorted order with all the numbers to the left of it. So we compare 18 and 72, and since 72 is bigger, we swap those numbers.
Next is 34. 34 is smaller than 72, so we should swap those two numbers. Then, we compare 34 with 18. 18 is smaller, so we're good there. Now you can see we're starting to form a sorted list on the left-hand side!
Next is the number 12, and we should continue the same process. 12 is smaller than 72, so we swap. Also smaller than 34, so swap. Also smaller than 18, so swap. Now we have 12 all the way on the left.
Now we do the same thing with the number 8, and it's a similar story to 12. After all the swaps, it ends up on the far-left side.
Finally, there's 16. We should compare and swap with 72, 34, and 18 in that order. Then, when we compare with 12, we find that 16 is larger. So we stop there.
And there you have it! A sorted list using the insertion sort algorithm.
Commenti