views:

218

answers:

1

A am studding for an Exam that I will have about sorting algorithms. And a Friend of mine gave me this code about LSD Radix Sort. And I don't 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 too much 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];
        }
    }   
}

}

+4  A: 

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.

Richard Fearn
Second time today someone has beat me to the punch answering a question by this OP! This is a good lesson on why you should comment your code, and also on why you should use named constants. For example, `int ASCII_VALUE_OF_LOWERCASE_A = 97` instead of just tossing 97 in the code on its own.
Lord Torgamus
Instead of introducing a constant `ASCII_VALUE_OF_LOWERCASE_A`, the character literal `'A'` could be used instead.
Richard Fearn