Counting Sort

Steps:


Code:
import java.util.Arrays;

class CountingSort {
        static public void countingSort(int[] in, int low, int high) {
                int[] count = new int[high-low+1];
                int[] out = new int[in.length];

                for(int i=0; i<in.length; i++) {
                        int inEle = in[i];

                        count[inEle-low] = count[inEle-low] + 1;
                }

                int sum = 0;
                for(int i=0; i<count.length; i++) {
                        sum = sum + count[i];
                        count[i] = sum;
                }

                for(int i= in.length-1; i>=0; i--) {
                        int inEle = in[i];

                        --count[inEle-low];

                        out[count[inEle-low]] = inEle;
                }

                System.out.println(Arrays.toString(out));
        }

        static public void main(String[] args) {
                int[] in = {4, 7, 2, 3, 3, 7, 5, 4};

                countingSort(in, 2, 7);
        }
}

eg:
Here we have 3 arrays:
   in: contains given input array elements
   count: This maintains the count of each element for the input array
   out: This is the destination array, in which the elements will be in sorted array

So the given input array is: {4, 7, 2, 3, 3, 7, 5, 4}
since the low is 2 and high is 7, we will have elements between 2-7(2/3/4/5/6/7) only the given input array. Since there are 5 possible numbers, we need to maintain a count array of length of 5(high-low+1)

Since elements are not starting from 0, but from 2: we store the count of 2 at 0th index, count of 3 at 1st index, ..., count of n at "n-low" index.

Now iterate over the input array from first element to last element.
Element: 4: increase the count of element 4 in count array: 4-low=4-2=2 ==> count[2] = count[2] + 1
Element 7: increase the count of element 5 in count array: 7-low=7-2=5 ==> count[5] = count[5] + 1
...
If we follow like this, we get the following count array:
{1, 2, 2, 1, 0, 1}

Sum elements of count array:
Now place the sum of previous elements and current element at current element at index.
==> {1, 3, 5, 6, 6, 7}

This count array indicates that: how many number of elements less than or equals to the current element are there in the given input array.
If we observer the above count array, at 3rd index, we have the count as 6. So there are 6 elements are present in the given input array that are <= 5(countIndex + low)

Constructing the output array:
We need to iterate over the input array from last element to first element.
Element 4: count[4-low] = count[4-2] = count[2] = 5. So there are 5 elements that are <= 5. Place the element 4 in the output array at 4th index(5-1)
==> out = {0, 0, 0, 4, 0, 0, 0}
Decrease the count[4] by 1 ==> count = {1, 3, 5, 6, 5, 7}

Element 5: count[5-low] = count[5-2] = count[3] = 6. So there are 6 elements that are <= 5. Place the element 5 in the output array at 5th index (6-1)
==> out = {0, 0, 0, 4, 5, 0, 0}
Decrease the count[5] by 1 ==> count = {1, 3, 5, 5, 5, 7}
...
Element 7==> out = {0, 0, 0, 4, 5, 0, 7} ==> count = {1, 3, 5, 5, 5, 6}, out = {0, 0, 0, 4, 5, 0, 7}
...
out = {2, 3, 3, 4, 4, 5, 7, 7}



Complexity Analysis:

References:
https://www.youtube.com/watch?v=5rLrRpcBCzo