2015/11/29

schemeでクイックソートとマージソート

こういうのを書いてなかったので.

;; クイックソート
(define (quick-sort lst)
  (if (null? lst)
      lst
      (let ((first (car lst)))
        (append (quick-sort (filter (lambda (x) (< x first)) (cdr lst)))
                (list first)
                (quick-sort (filter (lambda (x) (>= x first)) (cdr lst)))))))

;; マージソート
(define (merge-sort lst)
  (define (merge l m)
    (cond ((null? l) m)
          ((null? m) l)
          ((< (car l) (car m)) (cons (car l) (merge (cdr l) m)))
          (else
           (cons (car m) (merge l (cdr m))))))
  (define (divide lst)
    (if (or (null? lst) (null? (cdr lst)))
        lst
        (let* ((list-size (length lst))
               (half (floor (/ list-size 2))))
          (merge (divide (take lst half))
                 (divide (drop lst (- list-size half)))))))
  (divide lst))

© 2022 wat-aro