Sorting algorithms/Radix sort: Difference between revisions
→{{header|Scheme}}
Line 3,459:
=={{header|Scheme}}==
{{works with|R7RS}}▼
▲{{works with|R7RS}}
▲This implementation is for non-negative integers only.
<lang Scheme>;;; An illustrative implementation of the radix-10 example at
Line 3,516:
#(170 45 75 90 2 802 2 66)
#(2 2 45 66 75 90 170 802)</pre>
===An implementation using 9's-complements to support negative integers===
{{works with|R7RS}}
The following implementation does not support numbers of arbitrary magnitude, but it ''does'' work by converting signed integers to a lexicographically ordered representation, then reverting to the original representation.
<lang Scheme>;;; An illustrative implementation of the radix-10 example at
;;; https://en.wikipedia.org/w/index.php?title=Radix_sort&oldid=1070890278#Least_significant_digit
;;;
;;; This version sorts 9's-complements of the additive inverses of the
;;; integers, when converts the numbers back.
(cond-expand
(r7rs)
(chicken (import (r7rs))))
(import (scheme base))
(import (scheme write))
(define *max-magnitude* (make-parameter 999999))
(define (nines-complement x)
(let ((nines (+ (* 10 (*max-magnitude*)) 9)))
(- nines x)))
(define (sort-by-decimal-digit data power-of-10)
(define bins (make-vector 10 '()))
(do ((i (- (vector-length data) 1) (- i 1)))
((= i -1))
(let* ((element (vector-ref data i))
(digit (truncate-remainder
(truncate-quotient element power-of-10)
10)))
(vector-set! bins digit
(cons element (vector-ref bins digit)))))
(let ((non-zero-found
(let loop ((i 1))
(cond ((= i (vector-length bins)) #f)
((pair? (vector-ref bins i)) #t)
(else (loop (+ i 1)))))))
(when non-zero-found
(let ((i 0))
(do ((j 0 (+ j 1)))
((= j (vector-length bins)))
(do ((p (vector-ref bins j) (cdr p)))
((null? p))
(vector-set! data i (car p))
(set! i (+ i 1))))))
(not non-zero-found)))
(define (radix-sort data)
(define max-magnitude (*max-magnitude*))
(do ((i 0 (+ i 1)))
((= i (vector-length data)))
(let ((x (vector-ref data i)))
(if (negative? x)
(vector-set! data i (+ x max-magnitude))
(vector-set! data i (nines-complement
(- max-magnitude x))))))
(let loop ((power-of-10 1))
(let ((done (sort-by-decimal-digit data power-of-10)))
(unless done
(loop (* 10 power-of-10)))))
(do ((i 0 (+ i 1)))
((= i (vector-length data)))
(let ((x (vector-ref data i)))
(if (<= x max-magnitude)
(vector-set! data i (- x max-magnitude))
(vector-set! data i (- max-magnitude
(nines-complement x)))))))
(define data (vector-copy #(170 45 75 90 2 802 2 66)))
(write data)
(newline)
(radix-sort data)
(write data)
(newline)
(newline)
(set! data (vector-copy #(170 -45 75 -90 2 -802 2 -66)))
(write data)
(newline)
(radix-sort data)
(write data)
(newline)</lang>
{{out}}
<pre>$ chibi radix_sort_task-2.scm
#(170 45 75 90 2 802 2 66)
#(2 2 45 66 75 90 170 802)
#(170 -45 75 -90 2 -802 2 -66)
#(-802 -90 -66 -45 2 2 75 170)</pre>
=={{header|Sidef}}==
| |||