60604
klutometis
<string>foof-counting-sort</string>
(define (counting-sort! fortuita sortita max)
(let ((numerata (make-vector max 0)))
(loop count ((for x i (in-vector fortuita)))
(vector-set! numerata x (+ (vector-ref numerata x) 1))
(count))
(loop leq ((for x i (in-vector numerata 1)))
(vector-set! numerata i (+ x (vector-ref numerata (- i 1))))
(leq))
(loop sort ((for x i (in-vector-reverse fortuita)))
(let ((count-index (- (vector-ref numerata x) 1)))
(vector-set! sortita count-index x)
(vector-set! numerata x count-index))
(sort))))
(let* ((fortuita (vector 6 0 2 0 1 3 4 6 1 3 2))
(sortita (make-vector (vector-length fortuita))))
(let ((max (+ (apply max (vector->list fortuita)) 1)))
(counting-sort! fortuita sortita max)
sortita))
;;; #(0 0 1 1 2 2 3 3 4 6 6)
3419527104
#scheme
TRUE
2
Riastradh
<string>simplify</string>
(define (enumerate! fortuita numerata)
(loop ((for x (in-vector fortuita)))
(vector-set! numerata x (+ (vector-ref numerata x) 1))))
(define (leq! numerata)
(loop ((for x i (in-vector numerata 1)))
(vector-set! numerata i (+ x (vector-ref numerata (- i 1))))))
(define (sort! numerata sortita x)
(let ((count-index (- (vector-ref numerata x) 1)))
(vector-set! sortita count-index x)
(vector-set! numerata x count-index)))
(define (vector-max vector)
;; This will generate better code at the cost of assuming VECTOR to
;; be non-empty. The uncommented form will yield #F in that case.
;; (collect-maximum (initial (vector-ref vector 0))
;; (for x (in-vector vector 1))
;; x)
(collect-maximum (for x (in-vector vector))
x))
(define (make-numerata fortuita)
(make-vector (+ (vector-max fortuita) 1) 0))
(define (counting-sort fortuita)
(let ((sortita (make-vector (vector-length fortuita)))
(numerata (make-numerata fortuita)))
(enumerate! fortuita numerata)
(leq! numerata)
(loop ((for x (in-vector-reverse fortuita)))
(sort! numerata sortita x))
sortita))
3419597806
#scheme
TRUE
1
klutometis
<string>vector-max; non-destructive</string>
(define (enumerate! fortuita numerata)
(loop count ((for x (in-vector fortuita)))
(vector-set! numerata x (+ (vector-ref numerata x) 1))
(count)))
(define (leq! numerata)
(loop leq ((for x i (in-vector numerata 1)))
(vector-set! numerata i (+ x (vector-ref numerata (- i 1))))
(leq)))
(define (sort! numerata sortita x)
(let ((count-index (- (vector-ref numerata x) 1)))
(vector-set! sortita count-index x)
(vector-set! numerata x count-index)))
(define (vector-max vector)
(loop ((for x (in-vector vector))
(with max-x -inf.0 (max x max-x)))
=> max-x))
(define (make-numerata fortuita)
(let ((max (+ (vector-max fortuita) 1)))
(make-vector max 0)))
(define (counting-sort fortuita)
(let* ((sortita (make-vector (vector-length fortuita)))
(numerata (make-numerata fortuita)))
(enumerate! fortuita numerata)
(leq! numerata)
(loop sort ((for x (in-vector-reverse fortuita)))
(sort! numerata sortita x)
(sort))
sortita))
(let ((fortuita (vector 6 0 2 0 1 3 4 6 1 3 2)))
(counting-sort fortuita))
;; #(0 0 1 1 2 2 3 3 4 6 6)
3419533846
#scheme
TRUE