Schemeで破壊的クイックソート
一応できました。後は非破壊的クイックソートとのパフォーマンスの差を調べてみたいところです。
(define (_move_shift_one head tail)
(if (eq? (cdr head) tail)
(begin
(set-car! (cdr head) (car head)) ; shift one
head)
(_move_shift_one (cdr head) tail)))
(define (_move_shift head tail)
(if (eq? head tail)
head
(_move_shift head (_move_shift_one head tail))))
(define (moveBack src dst)
(let ((tmp (car src)))
(_move_shift dst src)
(set-car! dst tmp)
dst))
(define (sort! x)
(partial_sort! x ())
x)
(define (partial_sort! head tail)
(let ((pivot (split head (cdr head) tail)))
(if (eq? head pivot)
()
(partial_sort! head pivot))
(if (eq? (cdr pivot) tail)
()
(partial_sort! (cdr pivot) tail))))
(define (split pivot cur tail)
(if (eq? cur tail)
pivot
(if (< (car cur) (car pivot))
(begin
(moveBack cur pivot)
(split (cdr pivot) (cdr cur) tail))
(split pivot (cdr cur) tail))))
(define a '(3 2 4 1 5))
(sort! a) ;-> (1 2 3 4 5)
