8.8. Insertion Sort Code¶
Once again, taking the algorithm from something appropriate for a human to computer pseudocode requires adding more detail. In the code below, i
is equivalent to the black line - it marks the start of the unsorted portion of the list. j
is the right hand - it stores the location of the card that is being inserted into place. The animation of a human used the left hand to point to the card to the left of the one being inserted - here we use j - 1
to indicate the card to the left of the card being inserted. (Since j
is the index of a location, j - 1
gives us the index to its left.)
Note: assume that list already exists 1
i
= 2 i marks start of unsorted cards 2 repeat until (i
> length of thelist
): 3j
=i
j is location of current card 4 5 Note: swap current card left until it finds a home 6 repeat until (j
== 1) or (list[j]
>list[j - 1]
) 7 Note: Swap card to the left" 8temp
=list[j]
9list[j]
=list[j - 1]
10currentMin
=list[j]
11j
=j
- 1 current card has moved 12 13 Move the marker showing start of unsorted portion 14i
=i
+ 1
Like before, do not worry about memorizing the algorithm, instead use it and the animation below until you can consistently predict the next step before it runs and understand how i and j are getting used.
Why would we care about knowing more than one sorting algorithm? Each approach has its own advantages and disadvantages. Try clicking the “Reset - Partially Sorted” button and then run the sort on a list that is almost in order. Compare how insertion sort works on that list with how the selection sort does on the same list. Which one is more effective?