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")))))
6 ;qsort : (listof number) -> (listof number)
7 ;Uses generative recursion to quickly sort alon.
12 [(empty? (rest alon)) (list (first alon))]
13 [(<= (length alon) THRESHOLD) (srt alon)]
14 [else (append (qsort (smaller-items (first alon) (rest alon)))
16 (qsort (larger-items (first alon) (rest alon))))]))
18 ;smaller-items : number (listof numbers) -> (listof numbers)
19 ;Returns (listof numbers) of all those numbers in alon less than or equal to anumber.
21 (define (smaller-items anumber alon)
22 (filter (lambda (x) (<= x anumber)) alon))
24 ;larger-items : number (listof numbers) -> (listof numbers)
25 ;Returns (listof numbers) of all those numbers in alon larger than anumber.
27 (define (larger-items anumber alon)
28 (filter (lambda (x) (> x anumber)) alon))
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
36 [(cons? alon) (insert (first alon) (srt (rest alon)))]))
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)
43 [(empty? alon) (cons n empty)]
45 [(<= n (first alon)) (cons n alon)]
46 [(> n (first alon)) (cons (first alon) (insert n (rest alon)))])]))