FOR FREE MATERIALS

INTRODUCTION:

There are various sorting techniques in which counting sort is completely different from the others. In the case of most of the other sorting techniques, the values are compared with each other to get the sorted array whereas in the case of counting sort the sorting is done by calculating the frequency of each element of the array, and with that frequency, the sorted position is calculated by following some specific rules. As a whole, it is a simple sorting technique with less complexity than bubble, insertion, and many other sorting techniques.

ILLUSTRATION WITH EXAMPLE:

This procedure can work for positive or negative elements or a combination of both.

Suppose there are 5 elements in an array which is to be sorted in ascending order as shown below:

For sorting this array first we have to find the minimum and maximum element from the array. Here in this case the minimum element is -6 and the maximum element is 7.

Now the frequency of each element will be calculated and will be stored at the index as the same as the element. If the element is 1 then the frequency of ‘1’ will be calculated from the original array and will be stored at index 1 of the frequency calculating array. 

So the array to store the frequency of each element will be 7 - (-6) +1 = 14 and all the positions will be initialized to 0. The frequency of the element -6 will be stored in the index ‘0’ as arr[i] – min = index (-6 + 6 = 0) of the frequency calculating array as the array index cannot be negative. 

That means the index value of 7 will be (7 – (-6) = 14) 14 in the frequency calculating array. For the aforesaid example the frequency calculating array will be:

Index of -3 = -3 + 6 = 3  

Index of 7 = 7 + 6 = 13

Index of 2 = 2 + 6 = 8

Index of -6 = -6 + 6 = 0

Index of 7 = 7 + 6 = 13

Calculating index as frequency of element as arr[i] – min = index. 

After that the original sorted position of the array will be counted by adding two consecutive elements of the frequency calculating array as shown below:

After counting the frequency of each element. The elements of the original array will now be inserted into the output array according to its sorted position.

Example: 

We already calculated index of -3 is (-3 – (-6)) = 3) is 3. Now the value of index 3 is 2 (we got it after Cumulative count).  So, we calculate the index of the original array by subtracting 1 with content of frequency count array like index of -3 of original array will be 2 - 1 = 1.

In the same way, we can calculate the index of all elements of the original array.

Index of -6 of output array = content of count array of element – 6 (which is located at index 0 of count array as calculate above) minus 1 i.e. 1 - 1   = 0.

Index of  -3 of output array = 2 – 1 = 1.

Index of 2 of output array = 3 – 1  = 2.

Index of  7 of output array = 5 – 1  = 4.

Index of second 7 of output array = remaining content of index of 7 of count array i.e. 4 - 1 = 3

INPUT: An unsorted array arr[6,2,4,1,…………….,n]
OUTPUT: An sorted array arr[1,2,3,4,5,…………..,n] (in ascending order)
PROCESS:

Step 1: [Taking the number of elements and the array elements in the array ]
Read n
For i=0 to n repeat
	Read arr[i]
Step 2: [Find the maximum and minimum element of thearray ]
	Set max<-arr[0]
	Set min<-arr[0]
	for i=0 to n repeat
		if(arr[i]>max) then
			set max<-arr[i]
		else if(arr[i]<min) then
			set min<-arr[i]
Step 3: [creating the array to store the frequency of each element of the original array ]
	          Set range<-max-min+1;
	For i=0 to n repeat
		   Set pos[i]<-0
Step 4: [counting the frequency of each element ]
	         For i=0to n repeat
		Set pos[arr[i]-min]=pos[arr[i]-min]+1
Step 5: [counting the actual position of the elements in the sorted array]
        For i=1 to range repeat
		Set pos[i]<-pos[i]+pos[i-1]
Step 6: [creating the output array by putting the elements to their proper position]
	        For i=n-1 to 0 repeat
		Set op[pos[arr[i]-min]-1]<-arr[i]	
		Set pos[arr[i]-min]<-pos[arr[i]-min]-1


Step 7: [displaying the array element after sorting]
	         For i=0 to n repeat
			Print op[i]
Step 8: Stop.