...
- Example 7. Termination argument for
quick-sort
:Code Block ;; quick-sort list-of-number -> list-of-number ;; Purpose: (quick-sort lon) sorts lon into ascending order ;; ;; Examples: ;; (quick-sort empty) => empty ;; (quick-sort '(1)) => '(1) ;; (quick-sort '(1 4 3 5)) => '(1 3 4 5) ;; (quick-sort '(1 4 3 4 2 5)) => '(1 2 3 4 4 5) ;; ;; Termination: ;; On each call, quick-sort partitions the list alon into three sublists using ;; smaller-than, larger-than, and equal-to. The lists produced by smaller-than ;; and larger-than are sorted using recursive applications of quick-sort. Since ;; the lists produced by smaller-than and larger-than are strictly shorter than ;; alon (the given list), quick-sort terminates. (define (quick-sort alon) (cond [(empty? alon) empty] [else (append (quick-sort (smaller-items alon (first alon))) (equal-to alon (first alon)) (quick-sort (larger-items alon (first alon))))])) "Testing quick-sort:" ...
!! Access Permissions
- Set ALLOWTOPICCHANGE = Main.TeachersComp211Group