LSD Radix Sort for Integers

I'm having trouble wrapping my head around using radix sort for a group of fixed-length integers. In my below attempt to implement least significant digit radix sort, I have a function called num_at which returns the digit d in the number num. The code I've written has w = 2, where w represents the length of each number. (Essentially, then, this code is written for 3 digit numbers as my input below shows).

I modeled this off of key-indexed counting for each digit, but I'm getting an output of [0, 12, 32, 32, 44, 0] and frankly having a tough time following why. This is my input: [32,12,99,44,77, 12] I initiated the count array with 99 values because of all the possible values there can be between 0 - 99 in accordance with key indexed counting. Does anything here immediately jump out as incorrect? Also, is my num_at method the right way to do this or is there a better way?

def num_at(num, d)
    return num if num/10 == 0 
    a = num 
    #return the dth digit of num
    counter = 0 
    until counter == d 
        a/=10 
        counter += 1 
    end 

    a % 10
end

def radix_sort(arr)
    w = 2
    #count_arr can have any possible number from 0-99
    aux = Array.new(arr.length) {0}

    d = w-1
    while d >= 0 
        count = Array.new(99) {0}
        i = 0 

        #create freq arr
        while i < arr.length 
            count[num_at(arr[i], d) + 1] += 1 #offset by 1 
            i += 1 
        end 

        #compute cumulates 
        i = 0 
        while i < count.length - 1
            count[i + 1] += count[i]
            i += 1
        end 

        z = 0 
        #populate aux arr
        while z < arr.length 
            aux[num_at(arr[z], d)] = arr[z]
            count[num_at(arr[z], d)] += 1 
            z += 1
        end

        #override original arr
        z = 0 
        while z < arr.length 
            arr[z] = aux[z]
            z += 1
        end 
        d -= 1
    end

    arr
end

This is functioning Java code for LSD radix sort taken from a textbook that I'm trying to implement with Ruby:

public static void lsd(String[] a)
{
 int N = a.length;
 int W = a[0].length;
 for (int d = W-1; d >= 0; d--)
 {
 int[] count = new int[R];
 for (int i = 0; i < N; i++)
 count[a[i].charAt(d) + 1]++;
 for (int k = 1; k < 256; k++)
 count[k] += count[k-1];
 for (int i = 0; i < N; i++)
 temp[count[a[i].charAt(d)]++] = a[i];
 for (int i = 0; i < N; i++)
 a[i] = temp[i];
 }

and the pseudocode for key-indexed counting (which is being repeated for every char):

Task: sort an array a[] of N integers between 0 and R-1
Plan: produce sorted result in array temp[]
 1. Count frequencies of each letter using key as index
 2. Compute frequency cumulates
 3. Access cumulates using key as index to find record positions.
 4. Copy back into original array
 5. List item

LSD radix sort. Consider characters d from right to left  Stably sort
using dth character as the key via key-indexed counting.

The above java code / pseudocode information is pulled from this link: http://www.cs.princeton.edu/courses/archive/spring07/cos226/lectures/11RadixSort.pdf

链接地址: http://www.djcxy.com/p/70804.html

上一篇: 基于MSD排序算法的问题

下一篇: LSD基数排序整数