挿入ソート

写経しただけです。

(define (isort list cmp-fn)
  (define last (length list))
  (define (iter vec pos value)
    (let ((i (- pos 1)))
      (while (and (>= i 0) (cmp-fn (vector-ref vec i) value))
             (vector-set! vec (+ i 1) (vector-ref vec i))
             (set! i (- i 1)))
      (vector-set! vec (+ i 1) value)))
  (let ((i 1)
        (vec (list->vector list)))
    (while (< i last)
           (iter vec i (vector-ref vec i))
           (set! i (+ i 1)))
    (vector->list vec)))

(use gauche.test)
(test-start "sort")
(test-section "insert sort")
(define num-list '(3 9 6 5 1 9 4 7 4 1 2 0 2 4 1 5 0))
(define (numeric-cmp a b) (> a b))
(test* "num-list sort" '(0 0 1 1 1 2 2 3 4 4 4 5 5 6 7 9 9) (isort num-list numeric-cmp))
(set! num-list '(1 1 3 4 8 2 9 0 3 0 9 8 3 1 6 8))
(test* "num-list sort2" '(0 0 1 1 1 2 3 3 3 4 6 8 8 8 9 9) (isort num-list numeric-cmp))

(test-end)