Insertion Sort Algorithm
All sorting algorithms take a list of data (numbers, letters) and sort it into either ascending order with smallest number first and biggest number last or descending order (biggest number first). Note lists are often called Arrays.
Insertion works well for small lists, less so for larger ones. The best way to explain it is through an analogy (or watch the video at the bottom of the page):
Imagine you are playing a card game. You are dealt a card and you pick it up.
You are dealt your second card, you go to put it in your hand and ask yourself is it bigger or smaller than the first card -
If its smaller you put it to the left of the first card, if its larger you put it to the right.
You now get your third card, you compare this new card to the first card in your hand if the new card is smaller you put in the first card position (before card 1 in your hand) - if it isn't you move on and compare it to the second card - is it smaller - if so put it in position 2, if not move to the next card (there isn't one) so the new card goes in last position.
Insertion sort follows the same idea: Starting list: [4 ,7 ,8, 9, 2]
We take the first number
- First number is a 4 so >>> Sorted list [4] ---- still to be sorted [ 7 ,8, 9, 2]
- Next number is a 7.
- Is 7 less than 4? No, so it goes after this number..
>>>> Sorted list [4, 7] - still to be sorted [ 8, 9, 2]
- Next number is a 8.
- Is 8 less than 4 (in position 1) ? No, so it goes after this number..
- Is 8 less than 7 (in position 2) ? No, so it goes after this number..
>>>> Sorted list [4, 7, 8] - still to be sorted [ 9, 2]
- Next number is a 9.
- Is 9 less than 4 (in position 1) ? No, so it goes after this number..
- Is 9 less than 7 (in position 2) ? No, so it goes after this number.
- Is 9 less than 8 (in position 3) ? No, so it goes after this number..
>>>> Sorted list [4, 7, 8, 9] - still to be sorted [ 2]
- Next number is a 2
- Is 2 less than 4 (in position 1) ? yes, so it goes before this number, it is inserted in position 1..
>>>> Sorted list [2, 4, 7, 8, 9] - still to be sorted [ ] so list is sorted