
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort




Task

Sort an integer array with the   radix sort algorithm.

The primary purpose is to complete the characterization of sort algorithms task.




 
#lang Racket
(define (radix-sort l r)
  (define queues (for/vector #:length r ([_ r]) (make-queue)))
  (let loop ([l l] [R 1])
     (define all-zero? #t)
     (for ([x (in-list l)])
      (define x/R (quotient x R))
      (enqueue! (vector-ref queues (modulo x/R r)) x)
      (unless (zero? x/R) (set! all-zero? #f)))
    (if all-zero? l	
         (loop (let q-loop ([i 0])
                (define q (vector-ref queues i))
                (let dq-loop ()
                  (if (queue-empty? q)
                    (if (< i (sub1 r)) (q-loop (add1 i)) '())
                    (cons (dequeue! q) (dq-loop)))))
              (* R r)))))
(for/and ([i 10000]) ; run some tests on random lists with a random radix
  (define (make-random-list)
     (for/list ([i (+ 10 (random 10))]) (random 100000)))
  (define (sorted? l)
     (match l [(list) #t] [(list x) #t]
          [(list x y more ...) (and (<= x y) (sorted? (cons y more)))]))
  (sorted? (radix-sort (make-random-list) (+ 2 (random 98)))))
;; => #t, so all passed
 