# 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

• 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

## 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.

### 2 comments on “Counting Sort in Java”

• abhijith486279

For the information provided above about the counting array how comes the array size is taken as 10