| Paste number 60604: | foof-counting-sort |
| Pasted by: | klutometis |
| 5 days, 6 hours ago | |
| #scheme | Context in IRC logs | |
| Paste contents: |
| (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) |
Annotations for this paste:
| Annotation number 1: | vector-max; non-destructive |
| Pasted by: | klutometis |
| 5 days, 4 hours ago | |
| Context in IRC logs | |
| Paste contents: |
| (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) |
| Annotation number 2: | simplify |
| Pasted by: | Riastradh |
| 4 days, 11 hours ago | |
| Context in IRC logs | |
| Paste contents: |
| (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)) |