[racket] about HTDP quick-sort dead loop?

From: David Van Horn (dvanhorn at ccs.neu.edu)
Date: Fri Dec 9 05:11:15 EST 2011

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.


Posted on the users mailing list.