Counting Sort in Java

June 18, 2022

Counting Sort in Java

Counting Sort is a Integer-Sorting Algorithm, it is a bit-different and complicated from other comparison based sorting algorithms. Counting sort works efficiently on only positive integers, where it consider a Key element for various input values which are smaller than the key values, and falls in the range of 0-Key.

Counting Sort in JAVA Language

Counting Sort in Java

  • The strength of counting sort is that it is comparatively faster than other comparison-based algorithms.
  • It is reliable if the variation in keys is not significantly greater than the no. of elements.
  •  It is generally used as a sub-routine in radix sort and bucket sort to increase the productivity of those algorithms, as they work on comparatively larger data sets.
  •  Counting sort has a restriction of inputs when the ranges of the inputs are not known beforehand
Counting Sort in JAVA

Algorithm for counting sort in JAVA

  • Counting Sort (array P, array Q, int k)
  • For i ← 1 to k
  • do C [i] ← 0 [ θ(k) times]
  • for j ← 1 to length [A]
  • do C[A[j]] ← C [A [j]]+1 [θ(n) times]
    // C [i] now contain the number of elements equal to i
  • for i ← 2 to k
  • do C [i] ← C [i] + C[i-1] [θ(k) times]
    //C[i] now contain the number of elements ≤ i
  • for j ← length [A] down to 1 [θ(n) times]
  •  do B[C[A[j] ← A [j]
  • C[A[j] ← C[A[j]-1

Program for counting sort in JAVA

// Counting sort in Java programming

import java.util.Arrays;

class countSort {
    void applycountSort(int array[], int size) {
        int[] output = new int[size + 1];

        // Here we find the largest item in the array
        int max = array[0];
        for (int i = 1; i < size; i++) { if (array[i] > max)
                max = array[i];
        }
        int[] count = new int[max + 1];

        // Initialize the count for each element in array to 0
        for (int i = 0; i < max; ++i) {
            count[i] = 0;
        }

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

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

        // Search the index of each element of the actual array in count array, and 
        // place the elements in output array 
        for (int i = size - 1; i >= 0; i--) {
            output[count[array[i]] - 1] = array[i];
            count[array[i]]--;
        }

        // Transfer the sorted items into actual array
        for (int i = 0; i < size; i++) {
            array[i] = output[i];
        }
    }

    // Driver code
    public static void main(String args[]) {
        int[] data = {2, 5, 2, 8, 1, 4, 1};
        int size = data.length;

        countSort obj = new countSort();
        obj.applycountSort(data, size);

        System.out.println("Array After Sorting: ");
        System.out.println(Arrays.toString(data));
    }
}

Output

Array After Sorting: 
[1, 1, 2, 2, 4, 5, 8]

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting

2 comments on “Counting Sort in Java”