CountingSort with ArrayList

user3F5m1 0
Viewed 48

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.

counting-sort collections arraylist java algorithm
2 Answers

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.

Alexander Ivanchenko0

There are different ways to increment a primitive numerical variable, say, value.
value++ is one of them, additionally resulting in the value of value before the increment.
I'd have to read up whether the sequence between incrementing value and assigning to value in value = value++ is defined -
sanity advises to avoid it.
I use the increment operator where I intend next,
and value += 1 where I intend increase by 1.
(The other shortest one is ++value… yielding the value after increment.)

When incrementing the value in a List<Integer> values at a given index i, there are two possibilities:
either explicitly get() and set(), relying on auto-(un)boxing like Alexander Ivanchenko suggests,
or use a mutable Integer - java.util.concurrent.atomic.AtomicInteger has set(newValue), getAndIncrement() and incrementAndGet().

greybeard0
Related