Join the social network of Tech Nerds, increase skill rank, get work, manage projects...

• # Counting Sort

• 0
• 0
• 0
• 0
• 0
• 0
• 0
• 0
• 279
Comment on it

Hi,

This blog is to help you to understand counting sort in easiest manner, counting sort can sort the range in linear time but we have to provide the starting element and last highest element of the range (means elements in the range should be greater then or equal to starting point and should be less then or equal to limit value), extra space will be taken of order of the size of the range.

In Counting sort we maintain a count for each element inside our range and create a sorted range on the basis of it. Lets make it more simpler.

For example

Let we have our range is 2, 1, 2, 4, 0, 3, 1, 5

``int[] arr = new  int[] { 2, 1, 2, 4, 0, 3, 1, 5};``

we need an extra space to store the occurrence of every element inside the array (occurrence of 0, 1, 2, 3, 4, 5 has to be counted) so we need space of size 6 units.

``int[] count = new int[6];``

now we need to count the frequency of every element of the range and put it inside the count array.

``````arr     2 1 2 4 0 3 1 5

count   1 2 2 1 1 1

index   0 1 2 3 4 5``````

now we need to modify our count array such that in the updated array element at index i will be sum of itself and the element before it. for 1<= i < n-1.

``arr[ i ] = arr[ i ] + arr[ i - 1 ]``

now our count will be

``count   1 3 5 6 7 8``

now from this count array we will generate our sorted array by following these steps

we need to create a new array for the output of the size of the input range.

``int[] output = new int[8];``

traverse the elements of the input range and find the frequency of it. (first element is 2  considering it as index value for which we have count array value 5 )

at index count[2] - 1 ( 5 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

``````arr     2 1 2 4 0 3 1 5

count   1 3 5 6 7 8

index   0 1 2 3 4 5

output  0 0 0 0 2 0 0 0 ``````

after reducing the count value by 1

``count   1 3 4 6 7 8``

Next element inside input is 1

at index count[1] - 1  ( 3 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

``````arr     2 1 2 4 0 3 1 5

count   1 3 4 6 7 8

index   0 1 2 3 4 5

output  0 0 1 0 2 0 0 0 ``````

after reducing the count value by 1

``count   1 2 4 6 7 8``

Next element inside input is 2

at index count[2] - 1  ( 4 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

``````arr     2 1 2 4 0 3 1 5

count   1 2 4 6 7 8

index   0 1 2 3 4 5

output  0 0 1 2 2 0 0 0 ``````

after reducing the count value by 1

``count   1 2 3 6 7 8``

Next element inside input is 4

at index count[4] - 1  ( 7 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

``````arr     2 1 2 4 0 3 1 5

count   1 2 3 6 7 8

index   0 1 2 3 4 5

output  0 0 1 2 2 0 4 0 ``````

after reducing the count value by 1

``count   1 2 3 6 6 8``

Next element inside input is 0

at index count[0] - 1  ( 1 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

``````arr     2 1 2 4 0 3 1 5

count   1 2 3 6 6 8

index   0 1 2 3 4 5

output  0 0 1 2 2 0 4 0``````

after reducing the count value by 1

``count   0 2 3 6 6 8``

Next element inside input is 3

at index count[3] - 1  ( 6 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

``````arr     2 1 2 4 0 3 1 5

count   0 2 3 6 6 8

index   0 1 2 3 4 5

output  0 0 1 2 2 3 4 0 ``````

after reducing the count value by 1

``count   0 2 3 5 6 8``

Next element inside input is 1

at index count[1] - 1  ( 2 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

``````arr     2 1 2 4 0 3 1 5

count   0 2 3 5 6 8

index   0 1 2 3 4 5

output  0 1 1 2 2 3 4 0 ``````

after reducing the count value by 1

``count   0 1 3 5 6 8``

Next element inside input is 5

at index count[5] - 1  ( 8 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

``````arr     2 1 2 4 0 3 1 5

count   0 1 3 5 6 8

index   0 1 2 3 4 5

output  0 1 1 2 2 3 4 5 ``````

after reducing the count value by 1

``count   0 1 3 5 6 7``

Program for Count sort

``````public class CountSort {
public static void main(String[] args) {
// We considered our range from 0 to 9 in this case
int[] arr = new int[] { 1, 4, 1, 2, 7, 5, 2 };
int[] count = new int[10];
int[] output = new int[arr.length];

System.out.print("Input array : ");
for (int i : arr)
System.out.print(i + " ");
System.out.println();

//stroring the count of elements inside the input array
for (int i : arr)
count[i]++;

//adding previous index value in the new updated count array
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];

//puting values in output array
for (int i : arr) {
output[count[i]-1] = i;
--count[i];
}

System.out.print("Output array: ");
for (int i : output)
System.out.print(i + " ");
System.out.println();

}
}
``````

Output of the above program is

``````Input array : 1 4 1 2 7 5 2
Output array: 1 1 2 2 4 5 7
``````

Thanks :)

## 0 Comment(s)

OR
OR
Register

OR
Fill out the form below and instructions to reset your password will be emailed to you:

• Hire
• Post Projects

### Post Projects

• All at 0 Cost ....
• Post Tech Job
• Select Best Bidder
• Track the Project
• Approve Work and Pay safely
• Browse Nerds
• Work
• Find Projects Find Projects
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Manage
• Company Company

### Manage Company

• All at 0 Cost ....
• Manage Company and Employee Profiles
• Company wide Employee Productivity Reports
• Knowledge Sharing and Collaboration Tools
• Get Sales Lead and Bid for Tech Projects
• Send Invoices and Receive Payment Safely
• Learn
• Nerd Digest Nerd Digest
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
• Tech Q & A Tech Q & A
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General