Recollecting sort
Just made sure that I haven’t forgotten how to sort :–) First let me do it quick:
(define (qsort e)
(if (or (null? e) (<= (length e) 1)) e
(append (append (qsort (filter (cdr e) (lambda (x) (<= x (car e))))) (list (car e)))
(qsort (filter (cdr e) (lambda (x) (> x (car e))))))))This next version of qsort tries to get rid of the two passes to
filter the list but that made the code lengthier:
(define (qsort e)
(if (or (null? e) (<= (length e) 1)) e
(let loop ((left null) (right null)
(pivot (car e)) (rest (cdr e)))
(if (null? rest)
(append (append (qsort left) (list pivot)) (qsort right))
(if (<= (car rest) pivot)
(loop (append left (list (car rest))) right pivot (cdr rest))
(loop left (append right (list (car rest))) pivot (cdr rest)))))))Here is a version of merge-sort:
(define (split e)
(let loop ((f null) (r null) (i (/ (length e) 2)) (e e))
(if (not (null? e))
(if (> i 0)
(loop (cons (car e) f) r (sub1 i) (cdr e))
(loop f (cons (car e) r) i (cdr e)))
(cons (reverse f) (reverse r)))))
(define (merge a b)
(let loop ((res null) (a a) (b b))
(if (or (not (null? a)) (not (null? b)))
(cond
((and (not (null? a)) (not (null? b)))
(if (> (car a) (car b))
(loop (cons (car b) res) a (cdr b))
(loop (cons (car a) res) (cdr a) b)))
((not (null? a))
(loop (append (reverse a) res) null b))
(else
(loop (append (reverse b) res) a null)))
(reverse res))))
(define (merge-sort e)
(if (or (null? e) (<= (length e) 1)) e
(let* ((halves (split e))
(left (merge-sort (car halves)))
(right (merge-sort (cdr halves))))
(merge left right))))