Insertion Sort Algorithm
Goals
Students will understand elements of the insertion sort algorithm, which incrementally adds cards and swaps them into sorted order.
Video
Materials
One deck of Acorn cards.
Setup
Shuffle the deck and deal each student 8 cards.
Each student will shuffle their 8 cards, and place them in a face-down pile in front of you.
Algorithm
Take the top card from the pile, and place this card face-down. This card will be the start of your sorted collection. New cards will be added according to the following 3 steps.
-
First flip the right-most card in the collection face-up. Then take the top card from the pile and place it face-up to the right of the right-most card in the collection. If there are no more cards in the pile, then you are done.
-
If the two face-up cards are in order, such that the number of the left face-up card is less than the number in the right face-up card, then flip both cards face-down and return to step 1. If the two face-up cards are out of order, such that the number of the left face-up card is greater than the number in the right face-up card, then swap the two cards.
-
If there was a swap in step 2 and there is a face-down card to the left of the two face-up cards flip the face-down card to the left face-up, flip the right face-up card face-down, and repeat step 2. Otherwise, flip both cards face-down and return to step 1.
When all the cards have been added to the collection, flip them all face-up. The cards should be in sorted order, with the smallest cards on the left and largest on the right.
The cards in the collection are kept face-down as much as possible, and only two cards are face-up at a time. This emphasizes the way computers need to use indices to walk through an array and compare the data at neighboring memory locations.
Example
Here is an example of this algorithm applied to the cards 25, 06, 47, 54, 29, 35, 67, and 41.
Add 25
The first card 25 is placed face-down to start the collection.
Add 06
Next we flip up the right-most card 25. The next card 06 is placed to the right of our right-most card face-up.
The two face-up cards 25 and 06 are out of order because the left card 25 is greater than the right card 06, so here we must swap them.
After swapping, there is no card to the left of our two face-up cards, so we stop and flip them both face-down.
Add 47
Next we flip up the right-most card 25. The next card 47 is placed to the right of our right-most card face-up.
The two face-up cards 25 and 47 are in order because the left card 25 is less than the right card 47, so we stop and flip them both face-down.
Add 54
Next we flip up the right-most card 47. The next card 54 is placed to the right of our right-most card face-up.
The two face-up cards 47 and 54 are in order because the left card 25 is less than the right card 47, so we stop and flip them both face-down.
Add 29
Next we flip up the right-most card 54. The next card 29 is placed to the right of our right-most card face-up.
The two face-up cards 54 and 29 are out of order, so here we must swap them.
After swapping, there is a face-down card to the left of our two face-up cards so we flip our right card 54 face-down and flip the card to the left face-up.
The two face-up cards 47 and 29 are out of order, so here we must swap them.
After swapping, there is a face-down card to the left of our two face-up cards so we flip our right card 47 face-down and flip the card to the left face-up.
The two face-up cards 25 and 29 are in order, so we stop and flip them both face-down.
Add 35
Next we flip up the right-most card 54. The next card 35 is placed to the right of our right-most card face-up.
The two face-up cards 54 and 35 are out of order, so here we must swap them.
After swapping, there is a face-down card to the left of our two face-up cards so we flip our right card 54 face-down and flip the card to the left face-up.
The two face-up cards 47 and 35 are out of order, so here we must swap them.
After swapping, there is a face-down card to the left of our two face-up cards so we flip our right card 47 face-down and flip the card to the left face-up.
The two face-up cards 29 and 35 are in order, so we stop and flip them both face-down.
Add 67
Next we flip up the right-most card 54. The next card 67 is placed to the right of our right-most card face-up.
The two face-up cards 54 and 67 are in order, so we stop and flip them both face-down.
Add 41
Next we flip up the right-most card 67. The next card 41 is placed to the right of our right-most card face-up.
The two face-up cards 67 and 41 are out of order, so here we must swap them.
After swapping, there is a face-down card to the left of our two face-up cards so we flip our right card 67 face-down and flip the card to the left face-up.
The two face-up cards 54 and 41 are out of order, so here we must swap them.
After swapping, there is a face-down card to the left of our two face-up cards so we flip our right card 54 face-down and flip the card to the left face-up.
The two face-up cards 47 and 41 are out of order, so here we must swap them.
After swapping, there is a face-down card to the left of our two face-up cards so we flip our right card 47 face-down and flip the card to the left face-up.
The two face-up cards 35 and 41 are in order, so we stop and flip them both face-down.
Finished
We have no remaining cards in the pile so now we are done and can flip up all the cards to confirm they are in sorted order.
