Name sorting using counting sort

I'm having trouble sorting names in alphabetical order using counting sort, for instance I'm suppose to sort in alphabetical order and have number input added to it for example 0001 Alex Smith, Gregory John, Al开发者_开发百科ex Smith, Adam Richard, Alex Ryan. The output should be in this order:

Adam Richard

Alex Ryan

Alex Smith

Gregory John

My code so far:

public class Names 
{
    //private static int[] c;

 public ArrayList<String> getUserInput()
{
        ArrayList<String> names = new ArrayList<String>(); 
    Scanner in = new Scanner(System.in);
    while (in.hasNext()) 
     {
         names.add(in.next());  
        System.out.println(names); 
     }
      in.close();
    return names;
}
 private static CountingSort(int A[], int B[], int k[])
{
    int i;
    int C[0];
    for(i = 0; i <= k; i++){
        C[i]=0;
    }

    for(int j=1; j <= A.length; ){
        C[A[j]] = C[A[j]] + 1;
    }//C[i] now contains numbers of elements equals to i
    for(int i=1; i < k; i++){
        C[i] = C[i] + C[i - 1];

    }
    for(int j = A.length; j--){
    B[C[A[j]]] = A[j];
    C[A[j]] = C[A[j]] - 1;   
   }
}
}

Preparing Data

a. Make lengths of each string equal. Add ‘*’ at the end of each string to make all lengths equal.

Modified Data — [‘a*’, ‘bd’, ‘cd’, ‘ab’, ‘bb’, ‘a*’, ‘cb’]

b. Convert this modified data strings into numbers by assigning positional values to letters. a-z to 1–26 and * to 0. So this becomes 2-dimensional array.

Converted Data — [[1,0],[2,4],[3,4],[1,2],[2,2],[1,0],[3,2]]

Counting Sort

1. Create Count Array of n-dimensions where n=length of longest string (in this case 2) and, number of columns in each dimension = maximum value in ‘Converted Data’ (in this case 4) +1(added for ‘*’). So, a count array of 5x5 is created.

For example — if the longest length of string was 5 and highest character ‘f’ then an array of 7x7x7x7x7 would be created.

And just like normal count array, store values based on ‘Converted Data’. For example, for [1,0] the value stored is 2. Count Array

2. Cumulate this n-dimensional array starting from [0,0] all the way to [4,4].

3. Now similarly use the ‘Converted Data’ with Count Array to determine the position of each string in sorted array. For ex. — [1,0] (a*) the position is 2. And similarly after determining position, subtract 1 from that value in count array. So value at [1,0] in Count array becomes 1. Similarly position of [2,4] (bd) is 5 in sorted array.

https://playcode.io/475393

Counting sort is the wrong sorting algorithm for this problem. The counting sort algorithm is designed to sort integer values that are in a fixed range, so it can't be applied to sort strings.

On the other hand, you could use radix sort for this problem. Radix sort works by sorting the input one digit or character at a time, and it's very well-suited for sorting strings. There are two general flavors of radix sort - most-significant-digit radix sort and least-significant-digit radix sort. The MSD flavor of radix sort isn't too reminiscent of counting sort, but LSD radix sort works by using counting sort one character at a time. If you really must use counting sort, I'd recommend investigating LSD radix sort as an option.