Question

Je suis bonnettes pour un examen qui sera sur les algorithmes de tri. Un ami m'a donné ce code LSD Radix tri, et je ne comprends pas pourquoi il utilise les numéros 96,97 et 64? J'ai lu quelques petites choses sur le LSD genre Radix, mais je ne comprenais pas comment cela fonctionne.

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];
            }
        }   
    }
}
Était-ce utile?

La solution

97 est la valeur ASCII de la lettre 'a'. Si le caractère testé est une lettre minuscule, en soustrayant 96 de sa valeur ASCII donnera un nombre compris entre 1 et 26.

Dans le cas contraire, le caractère est supposé être une lettre majuscule. 65 est la valeur ASCII de la lettre « A », donc en soustrayant 64 va à nouveau donner une valeur comprise entre 1 et 26.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top