Gnome Sort Algorithm
Goals
Students will understand elements of the gnome sort algorithm, which incrementally swaps cards 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 row face-down to form a collection in front of you.
Algorithm
-
Flip the two left-most cards in the collection face-up.
-
If the two face-up cards are in order, continue to step 3. 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 is a face-down card to the left of the two face-up cards, then flip this card face-up, flip the right face-up card face-down, and repeat this step.
-
Check to see if there is a face-down card to the right of the two face-up cards. If so, then flip this card face-up, flip the left face-up card face-down, and repeat step 2.
When you reach the right side of the collection, flip all cards in the collection 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.
First we flip the two-left most cards in our collection face-up, 25 and 06.
These two cards 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 face-down card to the left of our two face-up cards so we continue.
There is a face-down card to the right of our two face-up cards so we flip our left card 06 face-down and flip the card to the right face-up.
The next two face-up cards are 25 and 47. These two cards are in order because the left card 25 is less than the right card 47 so here we do not need to swap and we continue.
There is a face-down card to the right of our two face-up cards so we flip our left card 25 face-down and flip the card to the right face-up.
The next two face-up cards are 47 and 54. These two cards are in order so here we do not need to swap and we continue.
There is a face-down card to the right of our two face-up cards so we flip our left card 47 face-down and flip the card to the right face-up.
The next two face-up cards are 54 and 29. These two cards 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 the card to the left face-up.
The next two face-up cards are 47 and 29. These two cards 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 the card to the left face-up.
The next two face-up cards are 25 and 29. These two cards are in order so we continue.
There is a face-down card to the right of our two face-up cards so we flip our left card 25 face-down and flip the card to the right face-up.
We continue through our collection comparing our face-up cards until there is a pair that is out of order
The next two face-up cards are 54 and 35. These two cards 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 the card to the left face-up.
The next two face-up cards are 47 and 35. These two cards 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 the card to the left face-up.
The next two face-up cards are 29 and 35. These two cards are in order so we continue.
There is a face-down card to the right of our two face-up cards so we flip our left card 25 face-down and flip the card to the right face-up.
We continue through our collection comparing our face-up cards until there is a pair that is out of order
The next two face-up cards are 67 and 41. These two cards 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 the card to the left face-up.
The next two face-up cards are 54 and 41. These two cards 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 the card to the left face-up.
The next two face-up cards are 47 and 41. These two cards 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 the card to the left face-up.
The next two face-up cards are 35 and 41. These two cards are in order so we continue.
There is a face-down card to the right of our two face-up cards so we flip our left card 35 face-down and flip the card to the right face-up.
We continue through our collection comparing our face-up cards until there is a pair that is out of order
The last two face-up cards 54 and 67 are in order and there is no face-down card to the right so we stop.
Finished
We can flip up all the cards and confirm they are in sorted order.
