LSD Radix Sort code in java
-
26-09-2019 - |
Question
I am studding for an Exam that will be about sorting algorithms. A Friend gave me this code about LSD Radix Sorting, and I don't understand why he is using the numbers 96,97 and 64? I've read a few things about LSD radix sort, but I didn't understand how it works.
public class LSDRadix {
private static String[] list;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine().trim());
int size=0;
list =new String[n];
for(int i=0; i<n; i++){
list[i]= sc.nextLine();
if(size < list[i].length()){
size = list[i].length();
}
}
sort(size);
for(int j=0; j<n;j++)
System.out.println(list[j]);
}
private static void sort(int sizes){
int numChars = 58;
String [] aux = new String[list.length];
int[] counter;
for(int i=sizes-1; i>=0 ;i--){
counter = new int[numChars];
for(int j=0; j<list.length; j++){
if(list[j].length() > i){
if(list[j].charAt(i) >= 97)
counter[list[j].charAt(i)-96]++;
else
counter[list[j].charAt(i)-64]++;
}else{
counter[0]++;
}
}
for(int j=0; j<numChars-1; j++){
counter[j+1] += counter[j];
}
for(int j=list.length-1; j>=0; j--){
if(list[j].length() > i){
int pos;
if(list[j].charAt(i) >= 97){
pos = list[j].charAt(i)-96;
}else{
pos = list[j].charAt(i)-64;
}
aux[counter[pos]-1] = list[j];
counter[pos]--;
}else{
aux[counter[0]-1] = list[j];
counter[0]--;
}
}
for(int j=0; j<list.length; j++){
list[j] = aux[j];
}
}
}
}
Solution
97 is the ASCII value for the letter 'a'. If the character being tested is a lower-case letter, subtracting 96 from its ASCII value will give a number between 1 and 26.
Otherwise, the character is assumed to be an upper-case letter. 65 is the ASCII value for the letter 'A', so subtracting 64 will again give a value between 1 and 26.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow