Page History

...

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

Child pages

Versions Compared

Old Version 10

New Version 11

Key

!! Access Permissions