CountingSort with ArrayList-CodePudding

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.

CodePudding user response：

By using a parameterized constructor of ArrayList which allows providing a capacity you're still getting an empty ArrayList. There diffence is it would have an underlying array of the desired size intead 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 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);
    value  ;
            
    count.set(index, value);
}

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.