DataStructure #2 : Counting Sort

Overview :
Counting sort is a sorting algorithm that works by counting the number of times each element appears in the input array. The counts are then used to create a sorted output array.

The counting sort algorithm works as follows:

1. Find the maximum value in the input array.

Input Array >> A = [5, 2, 3, 0, 11, 9, 6, 2]

Max value >> k = 11

2. Create an array of size equal to the maximum k + 1.

int[] count = new int[k + 1];

3. Initialize all elements of the count array to 0.

// Initialize the count array with all zeros.
    for (int i = 0; i < k; ++i) {
      count[i] = 0;
    }

count = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] >> size 12

4. Iterate through the input array, incrementing the count array at the index of each element.

iterate input array a[0] = 5 is the index for the count and how many times is value.

a[0] = 5 >> appear 1 time only so count [5] = 1 and iterate for input array.

count = [1, 0, 2, 1, 0, 1, 1, 0, 0, 1, 0, 1]

// Store the count of each element
    for (int i = 0; i < size; i++) {
      count[array[i]]++;
    }

5. Store the cumulative count of each array.

count [1] = count [1] + count [0] >> iterate from 1 to K

// Store the cumulative count of each array
    for (int i = 1; i <= k; i++) {
      count[i] = count[i] + count[i - 1];
    }

6. Create an output/result array with the length of the input array.

int[] output = new int[size + 1];

7. Find the index of each element of the original array in the count array, and Place the elements in the output array

//STEP 3 >> Find the index of each element of the original array in the count array, and
    //Place the elements in the output array
    for (int i = size - 1; i >= 0; i--) {
      output[count[array[i]] - 1] = array[i];
      count[array[i]]--;
    }

Here are the algorithms :

fun countingSort(inputSort:Array<Int>) {
    
  // array size
    val n = inputSort.size

    //Find maximum value from input array
    val max = inputSort.max()

    //Create a new array with (max +1 ) and initialise by 0
    val count = IntArray(max+1, { 0 }) 

/* Iterate input array and increase count value in count array at the index of input array
*  count[inputSort[i]] = count[inputSort[i]] +1
* OR 
* ++count[inputSort[i]]
 * */

    for(i in 0 ..n-1){
       ++count[inputSort[i]]
    }

   /* Iterate counter value for all counting array
   * */
    for(i in 1 ..max){
        count[i] = count[i] + count[i-1]
    }

   /*
   * Create a result array with the same input size n and update the value to result from decreasing order
   * */
    val result = IntArray(n, { 0 })
    for(i in n-1 downTo  0 ){
        result[ -- count[ inputSort[i]]] = inputSort[i]
    }

    // update result array into the original array
    for(i in 0 .. n-1 ){
        inputSort[i] = result[i]
    }
    println(inputSort.joinToString { "$it" })
}

array = [1, 5, 3, 2, 4]
sorted_array = counting_sort(array)
print(sorted_array)


Output:: [1, 2, 3, 4, 5]

The counting sort algorithm has the following time and space complexities:

Time complexity: O(n + r), where n is the number of elements in the input array and r is the range of values in the input array.
Space complexity: O(n + r), where n is the number of elements in the input array and r is the range of values in the input array.

Counting sort is a very efficient algorithm for sorting arrays of integers with a small range of values. However, it is not a good choice for sorting arrays of integers with a large range of values. This is because the count array can become very large, which can lead to poor performance.

Here are some of the advantages of counting sort:

1. It is a very efficient algorithm for sorting arrays of integers with a small range of values.
2. It is a stable sorting algorithm, which means that the relative order of equal elements is preserved in the sorted output array.
3. It is a simple algorithm to implement.

Here are some of the disadvantages of counting sort:

1. It is not a good choice for sorting arrays of integers with a large range of values.
2. It requires extra space to store the count array.
3. It is not a good choice for sorting arrays of real numbers.

Conclusion :

The counting sort is a stable sort, meaning that it preserves the original order of elements with equal keys. It is also an in-place sort, meaning that it does not require any additional space. Counting sort is a relatively efficient sorting algorithm for small integers, but it can be inefficient for large integers.

Thanks to :

https://www.youtube.com/watch?v=pEJiGC-ObQE