[racket] Stuck on HtDP 25.2.6

2010/10/25 Luke Jordan <luke.jordan at gmail.com>:

> Develop a variant of quick-sort that uses only one comparison function, say,
> <. Its partitioning step divides the given list alon into a list that
> contains the items of alon smaller than (first alon) and another one with
> those that are not smaller.
>
> Use local to combine the functions into a single function.

Step 1
---------

Combine these functions (taken from the text) into big function
using local.

;; 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]
    [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))]))


Step 2
---------

The function larger-items contains this subexpression

    (> (first alon) threshold)

change it to

    (<  threshold (first alon))

now both larger-items and smaller-items use the
same comparison function.

Step 3
----------
> Then abstract the
> new version to consume a list and a comparison function:


-- 
Jens Axel Søgaard