# [racket] Stuck on HtDP 25.2.6

 From: Jens Axel Søgaard (jensaxel at soegaard.net) Date: Mon Oct 25 18:34:15 EDT 2010 Previous message: [racket] Stuck on HtDP 25.2.6 Next message: [racket] there must be function right after parenthesis? Messages sorted by: [date] [thread] [subject] [author]

```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

```

 Posted on the users mailing list. Previous message: [racket] Stuck on HtDP 25.2.6 Next message: [racket] there must be function right after parenthesis? Messages sorted by: [date] [thread] [subject] [author]