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.
My question is how to revise it?
Best regards
mht
;; The first three lines of this file were inserted by DrRacket. They record
metadata
;; about the language level of this file in a form that our tools can easily
process.
#reader(lib "htdp-intermediate-reader.ss" "lang")((modname quicksort)
(read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp")))
(htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss"
"teachpack" "htdp")))))
;; quick-sort : (listof number) -> (listof number)
;; to create a list of numbers with the same numbers as
;; alon sorted in ascending order
;; assume that the numbers are all distinct
(define (quick-sort alon)
(cond
[(empty? alon) empty]
[(empty? (rest alon)) alon]
[else (append
(quick-sort (smaller-items alon (first alon)))
(list (first alon))
(quick-sort (larger-items alon (first alon))))]))
;; larger-items : (listof number) number -> (listof number)
;; to create a list with all those numbers on alon
;; that are larger than threshold
(define (larger-items alon threshold)
(cond
[(empty? alon) empty]
[else (if (> (first alon) threshold)
(cons (first alon) (larger-items (rest alon) threshold))
(larger-items (rest alon) threshold))]))
;; smaller-items : (listof number) number -> (listof number)
;; to create a list with all those numbers on alon
;; that are smaller than threshold
(define (smaller-items alon threshold)
(cond
[(empty? alon) empty]
[else (if (<= (first alon) threshold)
(cons (first alon) (smaller-items (rest alon) threshold))
(smaller-items (rest alon) threshold))]))
;; test
(quick-sort '(1 3 4 5 2 ))_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
