Counting Sort is a linear sorting algorithm with asymptotic complexity O(n+k), which was found by Harold Seward in 1954.
Counting Sort is very time efficient and stable algorithm for sorting. Unlike bubble sort and insertion sort, counting sort is not a comparison based algorithm. It avoids comparisons and exploits the O(1) time insertions and lookup in an array.
Counting Sort algorithm works on the keys that are small integer and lies between a specific range. It functions by counting the number of objects that have each distinct key value. Then it uses some arithmetic calculation to place each key value into a sorted sequence.
Its running time is O(Maximum key value – Minimum key value) which is linear. So it is useful only when a difference is not large.
Counting Sort is very time efficient and stable algorithm for sorting. Unlike bubble sort and insertion sort, counting sort is not a comparison based algorithm. It avoids comparisons and exploits the O(1) time insertions and lookup in an array.
Counting Sort algorithm works on the keys that are small integer and lies between a specific range. It functions by counting the number of objects that have each distinct key value. Then it uses some arithmetic calculation to place each key value into a sorted sequence.
Its running time is O(Maximum key value – Minimum key value) which is linear. So it is useful only when a difference is not large.
HERE ARE SOME KEY POINTS OF COUNTING SORT ALGORITHM –
 Counting Sort is a linear sorting algorithm.
 Time complexity of Counting Sort is O(n+k), where n is the size of the sorted array and k is the range of key values.
 It is not an inplace sorting algorithm as it requires extra additional space O(k).
 Counting Sort is stable sort as relative order of elements with equal values is maintained.
 Counting Sort is inefficient if the range of key value (k) is very large. If the input array is already sorted then also it will require an additional array to store the sorted elements and will process it completely.
 Counting Sort has a disadvantage that it can only sort discrete values like integer, as frequency range cannot be constructed for other values.
PSEUDOCODE OF COUNTING SORT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 CountingSort(A) //A[] Initial Array to Sort //Complexity: O(k) for i = 0 to k do c[i] = 0 //Storing Count of each element //Complexity: O(n) for j = 0 to n do c[A[j]] = c[A[j]] + 1 // Change C[i] such that it contains actual //position of these elements in output array ////Complexity: O(k) for i = 1 to k do c[i] = c[i] + c[i1] //Build Output array from C[i] //Complexity: O(n) for j = n1 downto 0 do B[ c[A[j]]1 ] = A[j] c[A[j]] = c[A[j]]  1 end func

0 Questions:
Post a Comment