CSC 216 F09/Sorting
Sorting
Background
Give the title of your exercise, which may include the name of the topic you are covering, or some other catchy title.
Discovering A Sorting Procedure
Too often, we teach beginning programming students how to sort. It is better if they discover how to sort on their own. We should encourage them to try sorting methods with cards and blocks and then have them develop written procedures..
Props
This can be accomplished by two blocks cut out with slots: the “ARRAY” block has five slots numbered 0 to 4, and the “HOLD” block has one slot. They also need five cards with numbers on them. Refer to the Figure 1.
Procedure
Have the students fill the ARRAY block with the five card and have them sort them with these rules:
1) You can move a card from any position to any empty slot. 2) You can only use one hand to move the cards.
As they explore different sorting approaches, they soon learn that swapping cards involves three steps: moving a card to a temporary slot, moving the other card, and moving the card from the temporary slot to the first slot. They also discover that they could compare two adjacent locations in an orderly manner from to back and swap them if necessary.
Whatever procedure they come up with, hopefully they will discover that either the smallest ends up in the front or the largest ends up in the back. Once this is established, hopefully, they will figure out that if they repeat the whole procedure 4 or 5 times that the ARRAY block will become sorted.
After they can sort five cards, have them write down the procedure that they used. Then shuffle the cards and test the procedure. A procedure might look like this: 1) Compare slot 0 and slot 1. If out of order, move what is in slot 0 to HOLD, move what is in slot 1 to slot 0, and move what is in HOLD to slot 1. 2) Compare slot 1 and slot 2. If out of order, do the same. 3) Do same for slots 2 and 3 and then slots 3 and 4. 4) Repeat all the steps 4 more times. 5) The result is a sorted deck.
This physical manipulation of cards in slots is easier to visualize than using tables or trying to write a program. Once they finalize the process and have it documented, then have them write the program to implement their procedure. Ignore inefficiencies. The desired outcome here is that they develop the method and that it really works. Since it is their method, they will feel better about debugging their own procedure.