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];
}
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))