// in-place radix-sort(a): queues = new queue[19]) // 19 for -9 to 9 passes = max(get-passes(max(a)), get-passes(min(a))) for pass = 0, < passes: radix-sort-pass(a, queues, pass) copy-to-a(queues, a) radix-sort-pass(a, queues, pass): for n in a: radix = get-radix(n, pass) queues[radix + 9].enqueue(n) // works for -ve n, -9 %10 = -9 get-radix(n, pass): while pass > 0 && n != 0: n = n /10 pass-- return n %10 copy-to-a(queues, a): i = 0 for q in queues: while !q.empty(): a[i++] = q.dequeue() get-passes(n): passes = 0 while n != 0: n = n /10 passes++ return passes

Time: O(nm) for m passes

## No comments:

## Post a Comment