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 |26.3|) (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 1. (quick-sort (list 10 6 8 9 14 12 3 11 14 16 2))
5 2. (append (quick-sort (list 6 8 9 3 2)) 
6            10
7            (quick-sort (list 14 12 11 14 16)))
8 3. (append (append (quick-sort (list 3 2))
9                    6
10                    (quick-sort (list 8 9))) 
11            10
12            (quick-sort (list 14 12 11 14 16)))
13 4. (append (append (append (quick-sort (list 2))
14                            3
15                            empty)
16                    6
17                    (quick-sort (list 8 9))) 
18            10
19            (quick-sort (list 14 12 11 14 16)))        
20 
21 5. (append (append (append (list 2)
22                            3
23                            empty)
24                    6
25                    (quick-sort (list 8 9))) 
26            10
27            (quick-sort (list 14 12 11 14 16)))
28 
29 6. (append (append (list 2 3)
30                    6
31                    (quick-sort (list 8 9))) 
32            10
33            (quick-sort (list 14 12 11 14 16)))
34 7. (append (append (list 2 3)
35                    6
36                    (append empty
37                            8
38                            (quick-sort (list 9)))) 
39            10
40            (quick-sort (list 14 12 11 14 16)))
41 
42 8. (append (append (list 2 3)
43                    6
44                    (append empty
45                            8
46                            (list 9))) 
47            10
48            (quick-sort (list 14 12 11 14 16)))
49 9. (append (append (list 2 3)
50                    6
51                    (list 8 9)) 
52            10
53            (quick-sort (list 14 12 11 14 16)))
54 
55 10. (append '(2 3 6 8 9) 
56             10
57             (quick-sort (list 14 12 11 14 16)))
58 
59 11. (append '(2 3 6 8 9) 
60             10
61             (append (quick-sort (list 12 11 14))
62                     14
63                     (quick-sort (list 16))))
64 12. (append '(2 3 6 8 9) 
65             10
66             (append (append (quick-sort (list 11))
67                             12
68                             (quick-sort (list 14)))
69                     14
70                     (quick-sort (list 16))))
71 13. (append '(2 3 6 8 9) 
72             10
73             (append (append (list 11)
74                             12
75                             (quick-sort (list 14)))
76                     14
77                     (quick-sort (list 16))))
78 14. (append '(2 3 6 8 9) 
79             10
80             (append (append (list 11)
81                             12
82                             (list 14))
83                     14
84                     (quick-sort (list 16))))
85 
86 15. (append '(2 3 6 8 9) 
87             10
88             (append '(11 12 14)
89                     14
90                     (quick-sort (list 16))))
91 
92 16. (append '(2 3 6 8 9) 
93             10
94             (append '(11 12 14)
95                     14
96                     (list 16)))
97 17. (append '(2 3 6 8 9) 
98             10
99             (append '(11 12 14)
100                     14
101                     '(16)))
102 18. (append '(2 3 6 8 9) 
103             10
104             '(11 12 14 14 16))
105 19. '(2 3 6 8 9 10 11 12 14 14 16) 
106 
107 The number of appends and quick-sorts is each (- (length alon) 1), or (- N 1).
108 
109 (quick-sort (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14))
110 (append empty
111         1
112         (quick-sort (list 2 3 4 5 6 7 8 9 10 11 12 13 14)))
113 
114 (append empty
115         1
116         (append empty
117                 2
118           (quick-sort (list 1 2 3 4 5 6 7 8 9 10 11 12 13 14))     
119                 (quick-sort (list 3 4 5 6 7 8 9 10 11 12 13 14))))