Many of you headed down complicated paths when asked to implement sort following the template today. Most of you ran into one of two (related) problems:
Templates defer questions about the logic/algorithm of a program until after its core structure is in place. If you know how to use the template, you get a lot of code written down that can then help you think out an algorithm. The design process becomes a lot more manageable.
Writing the template means writing the whole template, not just the cond (because as soon as you had that much you started thinking about the algorithm). The whole template for sort looked like
;; sort : list-of-number -> list-of-number[sorted] ;; sort list of numbers into increasing order (define (sort alon) (cond [(empty? alon) ...] [(cons? alon) ... (first alon) ... (sort (rest alon))]))
If you gave any thought to the sort algorithm before you had this much on paper, you started thinking about the algorithm too early.
Filling in the empty case was easy -- that came from the examples. What do you do in the cons case? Again, many of you started thinking about the algorithm, instead of thinking about what the template gave you for free. To use the template, ask yourself the following questions:
Answering the third question leads you to an algorithm: stick (or insert) the number into its appropriate place in a list of numbers. How do you do that? That sounds like a straightforward program on list of numbers (it is, and one you should certainly be able to write). Modify the template with a helper function name for this new algorithm you need, then write the insert helper function to finish sort.
;; sort : list-of-number -> list-of-number[sorted] ;; sort list of numbers into increasing order (define (sort alon) (cond [(empty? alon) empty] [(cons? alon) (insert (first alon) (sort (rest alon)))]))
Learning to ask yourself the template questions above (what does each piece give me and how do I combine them--use the contract and purpose to help) will dramatically improve your skills at working with templates. Internalize these questions.
Doesn't this suggest that you can never write a different sorting algorithm besides insertion sort? Tune in next time ...