Search code examples
javaalgorithmsortingradix-sort

explanation about a Java implementation of radix sort


I'm reading and learning about a Java implementation of radix sort, as shown below. It would be great if someone could clarify the logical meaning of pointTo, index and globalPtr.

https://www.hackerrank.com/challenges/string-similarity/editorial

private void radixSort0() {
    globalPtr = 0;
    Arrays.fill(bucketHead, -1);
    Arrays.fill(next, -1);

    for (int i = 0; i < n; i++) {
        int value = nr0[index[i]];
        if (bucketHead[value] == -1) bucketHead[value] = bucketTail[value] = globalPtr;
        else bucketTail[value] = next[bucketTail[value]] = globalPtr;
        pointTo[globalPtr++] = index[i];
    }

    int ptr = 0;
    for (int i = 0; i < M; i++)
        for (int j = bucketHead[i]; j != -1; j = next[j])
            index[ptr++] = pointTo[j];
}

Solution

  • This radixSort0() is not a complete radix sort. If your goal is to learn about radix sort, look elsewhere.
    In both (needlessly duplicated) radixSort methods, int[] next is used to establish singly linked lists - using indexes instead of references, and -1 instead of null. (You can not just set next[some_index_depending_on value] to index[i] - there would be no lists.) The int[] pointTo would probably be more descriptively be named value. Think of next&value as linked lists, represented in an instance with two data members of type array, as an alternative to an array of instances with members next&value. globalPtr is the smallest index not yet allocated in that/those array/s.

    (The blaring lack of comments in the code to follow is owing to my lack of understanding why anyone should try and construct a suffix array using this, or what the pieces of code contribute to that goal: feel free to correct&amend.)
    Not even thinking about testing, the Java way of handling this might be

    private void radixSortStep(int[]nr) {
        List<Integer> value[] = new List[M];
        for (int i = 0; i < value.length; i++)
            value[i] = new ArrayList<Integer>(0);
    
        for (int i: indexes)
            value[nr[i]].add(i);
    
        int ptr = 0;
        for (int i = 0; i < M; i++)
            for (int val: value[i])
                indexes[ptr++] = val;
    }
    

    (with a bit of hand-waving about M (set to n+1) and nr1 (initialise entries not copied from rank to n, not -1))