2010/10/25 Luke Jordan <luke.jor...@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
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
