Counting Sort Algorithm is an efficient sorting algorithm that can be used for sorting elements within a specific range. This sorting technique is based on the frequency/count of each element to be sorted and works using the following algorithm:
Consider the following input array A to be sorted. All the elements are in range 0 to 9.
A[]= {1, 3, 2, 8, 5, 1, 5, 1, 2, 7}
Initialize an auxiliary array, say count and store the frequency of every distinct element. Size of count is 10 (k+1, such that range of elements in A is 0 to k).
Figure 1: count array
Using the formula, updated count array is -
count[i] = Σcount[u] where 0 <= u <= i
Figure 2: Updated count array
Step 3: Add elements of array A to resultant array B using the following steps:
1. For, i=0, t=1, count[1]=3, v=2. After adding 1 to B[2], count[1]=2 and i=1
Figure 3: For i=0
2. For i=1, t=3, count[3]=6, v=5. After adding 3 to B[5], count[3]=5 and i=2
Figure 4: For i=1
3. For i=2, t=2, count[2]= 5, v=4. After adding 2 to B[4], count[2]=4 and i=3
Figure 5: For i=2
4. For i=3, t=8, count[8]= 10, v=9. After adding 8 to B[9], count[8]=9 and i=4
Figure 6: For i=3
On similar lines, we have the following:
Figure 7: For i=4
Figure 8: For i=5
Figure 9: For i=6
Figure 10: For i=7
Figure 11: For i=8
Figure 12: For i=9
Thus, array B has the sorted list of elements.
#include<iostream>
using namespace std;
int k=0; // for storing the maximum element of input array
/* Method to sort the array */
void sort_func(int A[],int B[],int n)
{
int count[k+1],t;
for(int i=0;i<=k;i++)
{
//Initialize array count
count[i] = 0;
}
for(int i=0;i<n;i++)
{
// count the occurrence of elements u of A
// & increment count[u] where u=A[i]
t = A[i];
count[t]++;
}
for(int i=1;i<=k;i++)
{
// Updating elements of count array
count[i] = count[i]+count[i-1];
}
for(int i=0;i<n;i++)
{
// Add elements of array A to array B
t = A[i];
B[count[t]] = t;
// Decrement the count value by 1
count[t]=count[t]-1;
}
}
int main()
{
int n;
cout<<"Enter the size of the array :";
cin>>n;
// A is the input array and will store elements entered by the user
// B is the output array having the sorted elements
int A[n],B[n];
cout<<"Enter the array elements: ";
for(int i=0;i<n;i++)
{
cin>>A[i];
if(A[i]>k)
{
// k will have the maximum element of A[]
k = A[i];
}
}
sort_func(A,B,n);
// Printing the elements of array B
for(int i=1;i<=n;i++)
{
cout<<B[i]<<" ";
}
cout<<"\n";
return 0;
}
Enter the size of the array: 10
Enter the array elements: 2 3 4 1 0 8 6 7 100 5
0 1 2 3 4 5 6 7 8 100
For scanning the input array elements, the loop iterates n times, thus taking O(n) running time. The sorted array B[] also gets computed in n iterations, thus requiring O(n) running time. The count array also uses k iterations, thus has a running time of O(k). Thus the total running time for counting sort algorithm is O(n+k).
Note: For a sorting algorithm to be stable, the order of elements with equal keys (values) in the sorted array should be the same as that of the input array.
Data Structures
Data Structures Overview Arrays Linked List Stack Queue Priority QueueExpression parsing
Infix Notation Prefix Notation Postfix notation Notation ConversionHashing
Hash Table and Function Collision ResolutionSearching Techniques
Linear Search Binary Search Interpolation Search Fibonacci SearchSorting
Bubble Sort Bubble Sort in Depth Selection Sort Selection Sort in Depth Insertion Sort Insertion Sort in Depth Shell Sort Merge Sort Quick Sort Quick Sort in Depth Counting Sort Radix Sort Bucket SortTree
Trees and Graphs Binary Tree Types of Binary Trees Binary Search Tree N-ary Tree AVL Tree Red Black Tree Splay tree B tree B+ treeTree Search Traversal Techniques
Breadth First Search (BFS) Depth First Search (DFS) Inorder, Preorder and Postorder TraversalHeaps
Heaps Introduction Binary Heap Heap OperationsTrending
C Programming
Remember to follow community guidelines and don't go off topic.