On 12/9/11 8:37 AM, mahaitao wrote:
Hi ,
When I read HTDP-Generative Recursion, I test quick-sort in Fig 68 and
all is right.
But when I try to replace "<" with "<=" in function "smaller-items" and
add new cond
"[(empty? (rest alon)) alon]" (do as the book Section 26 said), the new
quick-sort doesn't work and
run in a dead loop.
There are two unrelated changes going on that you shouldn't tangle together:
(1) replacing `<' with `<=' in `smaller-items'
(2) adding a cond-clause to `quick-sort' for the 1-element list case
Part (1): The code for `smaller-items' in section 26 is illustrating
what can go wrong when the problem generation step of a generative
recursion design goes wrong, so you are seeing the intended loop
behavior. The problem is the alternative `smaller-items' that uses `<='
instead of `<' generates problems that are no easier to solve than the
original problem in some cases.
Read the termination argument given for `quick-sort'. Is it a valid
argument when `smaller-items' uses `<='?
Part (2): The additional cond clause is being added to make explicit a
fact about `quick-sort' that was implicit in the original version,
namely that (quick-sort (list N)) = (list N), for all numbers N. This
additional case does not change the function, but it does make more
knowledge about the function explicit in its definition.
David
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
