1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |25.2|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 (define THRESHOLD 5)
5 
6 ;qsort : (listof number) -> (listof number)
7 ;Uses generative recursion to quickly sort alon.
8 
9 (define (qsort alon)
10   (cond
11     [(empty? alon) empty]
12     [(empty? (rest alon)) (list (first alon))]
13     [(<= (length alon) THRESHOLD) (srt alon)]
14     [else (append (qsort (smaller-items (first alon) (rest alon)))
15                   (list (first alon))
16                   (qsort (larger-items (first alon) (rest alon))))]))
17 
18 ;smaller-items : number (listof numbers) -> (listof numbers)
19 ;Returns (listof numbers) of all those numbers in alon less than or equal to anumber.
20 
21 (define (smaller-items anumber alon)
22   (filter (lambda (x) (<= x anumber)) alon))
23 
24 ;larger-items : number (listof numbers) -> (listof numbers)
25 ;Returns (listof numbers) of all those numbers in alon larger than anumber.
26 
27 (define (larger-items anumber alon)
28   (filter (lambda (x) (> x anumber)) alon))
29 
30 ;; sort : list-of-numbers  ->  list-of-numbers (sorted)
31 ;; to create a list of numbers with the same numbers as
32 ;; alon sorted in descending order
33 (define (srt alon)
34   (cond
35     [(empty? alon) empty]
36     [(cons? alon) (insert (first alon) (srt (rest alon)))]))
37 
38 ;; insert : number list-of-numbers (sorted)  ->  list-of-numbers (sorted)
39 ;; to create a list of numbers from n and the numbers on
40 ;; alon that is sorted in descending order; alon is sorted
41 (define (insert n alon)
42   (cond
43     [(empty? alon) (cons n empty)]
44     [else (cond
45             [(<= n (first alon)) (cons n alon)]
46             [(>  n (first alon)) (cons (first alon) (insert n (rest alon)))])]))