Sorting algorithms/Radix sort: Difference between revisions

Content added Content deleted
Line 3,521: Line 3,521:




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.
The following implementation converts signed integers to a lexicographically ordered representation (specifically, unsigned numbers in the correct order). It then sorts the lexicographically ordered representation, and finally converts back to the original representation.


<lang Scheme>;;; An illustrative implementation of the radix-10 example at
<lang Scheme>;;; An illustrative implementation of the radix-10 example at
Line 3,532: Line 3,532:
(import (scheme base))
(import (scheme base))
(import (scheme write))
(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 (sort-by-decimal-digit data power-of-10)
Line 3,565: Line 3,559:


(define (radix-sort data)
(define (radix-sort data)
(define max-magnitude (*max-magnitude*))
(define offset 0)

(do ((i 0 (+ i 1)))
(do ((i 0 (+ i 1)))
((= i (vector-length data)))
((<= (vector-length data) i))
(let ((x (vector-ref data i)))
(let ((x (vector-ref data i)))
(if (negative? x)
(when (negative? x)
(vector-set! data i (+ x max-magnitude))
(set! offset (max offset (- x))))))

⚫
(vector-set! data i (nines-complement
(do ((i 0 (+ i 1)))
(- max-magnitude x))))))
⚫
((= i (vector-length data)))
⚫
(vector-set! data i (+ (vector-ref data i) offset)))

(let loop ((power-of-10 1))
(let loop ((power-of-10 1))
(let ((done (sort-by-decimal-digit data power-of-10)))
(let ((done (sort-by-decimal-digit data power-of-10)))
(unless done
(unless done
(loop (* 10 power-of-10)))))
(loop (* 10 power-of-10)))))

(do ((i 0 (+ i 1)))
(do ((i 0 (+ i 1)))
((= i (vector-length data)))
((= i (vector-length data)))
(let ((x (vector-ref data i)))
(let ((x (vector-ref data i)))
⚫
(vector-set! data i (- (vector-ref data i) offset)))))
(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)))
(define data (vector-copy #(170 45 75 90 2 802 2 66)))
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Radix_sort"