[SOLVED] CountingSort with ArrayList

CountingSort with ArrayList

I'm trying to implement the Counting Sort algorithm with an ArrayList but I have some difficulties.

I in this piece of code I want to calculate the occurrence of each element in the ArrayList named l.

My code:

List<Integer> l = // initializing the given list

/** initialize the occurrence of each element in the count array **/

List<Integer> count = new ArrayList<>(max-min+1);

for(int i = 0; i < l.size(); i++){
    
    //count[arr[i]-min]++;

    int index = l.get(i) - min; //ok
    int value = 0;
    value = value++;
    count.set(index, value);
}

I can't find out how to perform the increment.

Solution

By using a parameterized constructor of ArrayList which allows providing a capacity you're still getting an empty ArrayList. The difference is that it would have an underlying array of the desired size instead of the default size of 10.

But you still have no elements to access. In order to populate ArrayList with default values, you can use another parameterized constructor that allows to provide a collection.

To create a light-weight auxiliary list of size max - min + 1 filled with zero integers (which would be passed to the constructor) you can use the utility method Collections.nCopies():

List<Integer> count = new ArrayList<>(Collections.nCopies(0, max - min + 1));

for (int i = 0; i < l.size(); i++) {
    int index = l.get(i) - min;
            
    int value = count.get(index);
    count.set(index, value + 1);
}

Note that implementing Counting sort by using ArrayList instead of a plane array, frankly saying, isn't very convenient. If it's an assignment requirement or self-imposed challenge - make sure that you understand how to implement the algorithm using arrays.