1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
 2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
 3 12687dd9 2023-08-04 jrmu #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 12687dd9 2023-08-04 jrmu (define THRESHOLD 5)
 5 12687dd9 2023-08-04 jrmu 
 6 12687dd9 2023-08-04 jrmu ;qsort : (listof number) -> (listof number)
 7 12687dd9 2023-08-04 jrmu ;Uses generative recursion to quickly sort alon.
 8 12687dd9 2023-08-04 jrmu 
 9 12687dd9 2023-08-04 jrmu (define (qsort alon)
10 12687dd9 2023-08-04 jrmu   (cond
11 12687dd9 2023-08-04 jrmu     [(empty? alon) empty]
12 12687dd9 2023-08-04 jrmu     [(empty? (rest alon)) (list (first alon))]
13 12687dd9 2023-08-04 jrmu     [(<= (length alon) THRESHOLD) (srt alon)]
14 12687dd9 2023-08-04 jrmu     [else (append (qsort (smaller-items (first alon) (rest alon)))
15 12687dd9 2023-08-04 jrmu                   (list (first alon))
16 12687dd9 2023-08-04 jrmu                   (qsort (larger-items (first alon) (rest alon))))]))
17 12687dd9 2023-08-04 jrmu 
18 12687dd9 2023-08-04 jrmu ;smaller-items : number (listof numbers) -> (listof numbers)
19 12687dd9 2023-08-04 jrmu ;Returns (listof numbers) of all those numbers in alon less than or equal to anumber.
20 12687dd9 2023-08-04 jrmu 
21 12687dd9 2023-08-04 jrmu (define (smaller-items anumber alon)
22 12687dd9 2023-08-04 jrmu   (filter (lambda (x) (<= x anumber)) alon))
23 12687dd9 2023-08-04 jrmu 
24 12687dd9 2023-08-04 jrmu ;larger-items : number (listof numbers) -> (listof numbers)
25 12687dd9 2023-08-04 jrmu ;Returns (listof numbers) of all those numbers in alon larger than anumber.
26 12687dd9 2023-08-04 jrmu 
27 12687dd9 2023-08-04 jrmu (define (larger-items anumber alon)
28 12687dd9 2023-08-04 jrmu   (filter (lambda (x) (> x anumber)) alon))
29 12687dd9 2023-08-04 jrmu 
30 12687dd9 2023-08-04 jrmu ;; sort : list-of-numbers  ->  list-of-numbers (sorted)
31 12687dd9 2023-08-04 jrmu ;; to create a list of numbers with the same numbers as
32 12687dd9 2023-08-04 jrmu ;; alon sorted in descending order
33 12687dd9 2023-08-04 jrmu (define (srt alon)
34 12687dd9 2023-08-04 jrmu   (cond
35 12687dd9 2023-08-04 jrmu     [(empty? alon) empty]
36 12687dd9 2023-08-04 jrmu     [(cons? alon) (insert (first alon) (srt (rest alon)))]))
37 12687dd9 2023-08-04 jrmu 
38 12687dd9 2023-08-04 jrmu ;; insert : number list-of-numbers (sorted)  ->  list-of-numbers (sorted)
39 12687dd9 2023-08-04 jrmu ;; to create a list of numbers from n and the numbers on
40 12687dd9 2023-08-04 jrmu ;; alon that is sorted in descending order; alon is sorted
41 12687dd9 2023-08-04 jrmu (define (insert n alon)
42 12687dd9 2023-08-04 jrmu   (cond
43 12687dd9 2023-08-04 jrmu     [(empty? alon) (cons n empty)]
44 12687dd9 2023-08-04 jrmu     [else (cond
45 12687dd9 2023-08-04 jrmu             [(<= n (first alon)) (cons n alon)]
46 12687dd9 2023-08-04 jrmu             [(>  n (first alon)) (cons (first alon) (insert n (rest alon)))])]))