Sunday, April 19, 2015

radix sort

Simple implementation of radix sort (LSB) with queues. Works for -ve numbers too as -12 %10 is -2. So 19 queues, for -9 to 9.
// 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