Counting Sort

Sahith Reddy

3 min readApr 9, 2022

Introduction:

· A non-comparison sorting algorithm is Counting Sort.

· In this Sorting will be done according to keys.

· Sorting will be done according to keys in this case.

· Counting Sort involves two steps:

1)Count the number of different elements in the array.

2)Calculate each element’s position in the sorted array.

Example:

1) Taken an array a of size(n) = 8 and max(k) = 6.

2) Take new array c of size k and count every distinct element in array a and add it to the index of that key values in array c.

3) After adding the count of every distinct element in c now do the sum of every two preceding key values from index 0 to k.

4) Now take a new array b of size n. now take the key value of array a from the last index after that go to the c array of that key-value index and subtract the key value of c by -1.

5) The value that we got by subtracting will be the index of b where the key value of the last element is placed.

6) Similarly do for all the key values by taking each from the last index of a.

7) Finally, we get the sorted array b.

Algorithm:

· Counting sort algorithm contains 4 for loops.

· loop1: Here we are counting the distinct elements by taking each element as a[i] and incrementing that index by 1.

· loop2: In this loop, we do the sum of every two preceding key values of array c from index 0 to k.

· loop3: This loop is for building array b i =n-1 because of taking the elements from the last index of a.in this loop we are using the c array to find the position in which index of b, the key value should be placed.