Sorting algorithms/Radix sort: Difference between revisions
Content added Content deleted
Line 3,459: | Line 3,459: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
<lang Scheme>;;; An illustrative implementation of the radix-10 example at |
<lang Scheme>;;; An illustrative implementation of the radix-10 example at |
||
Line 3,516: | Line 3,516: | ||
#(170 45 75 90 2 802 2 66) |
#(170 45 75 90 2 802 2 66) |
||
#(2 2 45 66 75 90 170 802)</pre> |
#(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}}== |
=={{header|Sidef}}== |