Comp 210 Lab 6: Sorting Code

Table of Contents

Quicksort

(define qSort
  (lambda (l)
    (cond ((null? l) null)
	  (else (append (qSort (lesser l (car l)))
			(equal-to l (car l))
			(qSort (greater l (car l))))))))

(define lesser
  (lambda (l e)
    (gather l < e)))

(define greater
  (lambda (l e)
    (gather l > e)))

(define equal-to
  (lambda (l e)
    (gather l = e)))

(define gather
  (lambda (data test reference)
    (cond ((null? data) null)
	  (else (if (test (car data) reference)
		    (cons (car data) (gather (cdr data) test reference))
		    (gather (cdr data) test reference))))))

Insertion Sort

(define iSort
  (lambda (alon)
    (cond ((null? alon) null)
	  (else (insert (car alon) (iSort (cdr alon)))))))

(define insert
  (lambda (n aslon)
     (cond
	((null? aslon) (list n))
        (else (if (< n (car aslon))
                  (cons n aslon)
                  (cons (car aslon)
                        (insert n (cdr aslon))))))))

Merge Sort

;; (merge-sort lyst)
;; lyst is a list of numbers
;; return a list with the same elements in ascending order
;;
(define merge-sort
  (lambda (lyst)
    (car (help-merge (separate lyst)))))


;; separate
;; given a list of elements l,
;; return a list of lists, each sublist a singleton containing
;; one of the elemnts of l.
;;
;; Example:
;; (separate (list 5 1 2)) = (list (list 5) (list 1) (list 2))
;;
(define separate
  (lambda (l)
    (cond [(null? l) null]
	  [else (cons (list (car l))
		      (separate (cdr l)))])))


;; (help-merge lolon)
;; lolon is a list of sorted lists of numbers.
;; Repeatedly call merge-pairs until only one list left.
;;
;; Example:
;;     (help-merge (list (list 5) (list 1) (list 2)))
;;   = (list (list 1 2 5))
;;
(define help-merge
  (lambda (lolon)
    (cond [(null? lolon) (list null)]
	  [(null? (cdr lolon)) lolon]
	  [else (help-merge (merge-pairs lolon))])))


;; (merge-pairs lolon)
;; lolon is a list of sorted list of numbers
;; Return a new list where every pair of lists
;; is replaced by those two lists merged and sorted.
;; That is, do one step of the merging.
;;
;; (Beware any unpaired list at the end of lolon.)
;;
;; Example:
;;     (merge-pairs (list (list 5) (list 1) (list 2)))
;;   = (list (list 5 1) (list 2))
;;
;;
(define merge-pairs
  (lambda (lolon)
    (cond [(null? lolon) null]
	  [(null? (cdr lolon)) lolon]
	  [else (cons
		 (merge-two (car lolon) (cadr lolon))
		 (merge-pairs (cddr lolon)))])))


;; (merge-two l1 l2)
;; l1, l2 are ascending lists of numbers
;; return a single ascending list of the numbers of of l1,l2.
;;
;; Example:
;;    (merge-two (list 3 8 11) (list 1 3 4 9 29))
;;  = (list 1 3 3 4 8 9 11 29)
;;
(define merge-two
  (lambda (l1 l2)
    (cond [(null? l1) l2]
	  [(null? l2) l1]
	  [(> (car l1) (car l2))
	   (cons (car l2) (merge-two l1 (cdr l2)))]
	  [else (cons (car l1) (merge-two (cdr l1) l2))])))

Generating Test Lists

(define make-list
  (lambda (n next-rule start)
    (cond ((= n 0) null)
	  (else (let ((next (next-rule start)))
		  (cons start (make-list (- n 1) next-rule next)))))))

(define nums-up
  (lambda (n)
    (make-list n add1 1)))

(define nums-down
  (lambda (n)
    (make-list n sub1 n)))


(define rand-max 32767)

(define nums-rand
  (lambda (n)
    (make-list n (lambda (x) (random rand-max)) (random rand-max))))