CODEWITHSUNDEEP
javasorting
Hash
Hash

Reputation: 39

trouble implementing counting sort for strings

I get this error when I attempt to sort it based off the second char in the string but it runs fine when I use the first char

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 8 at StringCountSort.countingSort(StringCountSort.java:27) at StringCountSort.main(StringCountSort.java:38)

import java.util.Arrays;

public class StringCountSort{
    
    public static void countingSort(String[] array, int size, int digit)
    {

        String[] result = new String[size+1];
        
        int maximum = 122;
        
        int[] count = new int[maximum + 1];
        for (int i = 0; i < count.length; i++){
            count[i] = 0;
        }
        
        for (int i = 0; i < size; i++){
            count[array[i].charAt(digit)] +=1;
        }
        
        for (int i = 1; i < count.length; i++){
            count[i] += count[i-1];
        }
    
        for (int i = size -1; i >= 0; i--){

            result[count[array[i].charAt(digit)] - 1] = array[i];
            count[array[i].charAt(0)]--;
        }

        for (int i = 0; i < size; i++) {
            array[i] = result[i];
        }
    }
    
    public static void main(String args[]){
        String[] data = { "eg", "fa", "bz", "ch", "hv", "df", "ag" };
        StringCountSort.countingSort(data, data.length, 1);
        System.out.println("Sorted Array in Ascending Order: ");
        System.out.println(Arrays.toString(data));
        
        
        
    }
}

line 28 result[count[array[i].charAt(digit)] - 1] = array[i]; 

line 37 StringCountSort.countingSort(data, data.length, 1);

Upvotes: 1

Views: 194

Answers (2)

Tobias Miosczka
Tobias Miosczka

Reputation: 213

Change

count[array[i].charAt(0)]--;

to

count[array[i].charAt(digit)]--;

This should do the trick.

I also suggest the following improvements:

  1. You don't need to pass the length of array as an argument.
  2. You don't need to set every int of count to 0;
  3. maximum should be Character.MAX_VALUE, to support every possible character.

The finished function could look like this:

    public static void countingSort(String[] array, int digit) {
        String[] result = new String[array.length];
        int[] count = new int[Character.MAX_VALUE + 1];

        for (int i = 0; i < array.length; i++){
            count[array[i].charAt(digit)]++;
        }
        for (int i = 1; i < count.length; i++){
            count[i] += count[i-1];
        }
        for (int i = array.length -1; i >= 0; i--){
            result[count[array[i].charAt(digit)] - 1] = array[i];
            count[array[i].charAt(digit)]--;
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = result[i];
        }
    }

Upvotes: 1

vishwampandya
vishwampandya

Reputation: 1167

Things that need to be changed are (if you want to sort the strings on the basis of first character)

  1. count[array[i].charAt(digit)] +=1 to count[array[i].charAt(0)] +=1
  2. result[count[array[i].charAt(digit)] - 1] = array[i]; count[array[i].charAt(0)]--; to result[--count[array[i].charAt(0)]] = array[i];

If you want to sort the string on the basis of the second character then simply change :

  1. count[array[i].charAt(0)]--; to count[array[i].charAt(digit)]--;

Upvotes: 0

Related Questions