Thursday, 16 November 2017

COUNTING SORT – EXPLANATION, PSEUDOCODE AND IMPLEMENTATION

Leave a Comment
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.

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 in-place 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[i-1]
 
  //Build Output array from C[i]
  //Complexity: O(n)
  for j = n-1 downto 0 do
  B[ c[A[j]]-1 ] = A[j]
  c[A[j]] = c[A[j]] - 1
end func

ASYMPTOTIC ANALYSIS OF COUNTING SORT

In this algorithm, the initialization of the count array and the loop which performs a prefix sum on the count array takes O(k) time. And other two loops for initialization of the output array takes O(n) time. Therefore, the total time complexity for the algorithm is : O(k)+ O(n)+ O(k)+ O(n)= O(n+k).
Worst Case Time complexity: O (n+k)
Average Case Time complexity: O(n+k)
Best Case Time complexity: O(n+k)
Space Complexity: O(k)
Data Structure: Array
Sorting In Place: No
Stable: Yes
Implementation of Counting Sort in C and Java programming language
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/* C implementation Counting Sort */
#include <stdio.h>
 
/*  Counting sort function  */
void counting_sort(int A[], int k, int n)
{
    int i, j;
    int B[n], C[k+1];
 
    //Initializing counting array C[i] to 0
    for (i=0; i<=k; i++)
        C[i] = 0;
    //Store count of each element in array C
    for (j=0; j<n; j++)
        C[A[j]] = C[A[j]] + 1;
 
    /* Change C[i] such that it contains actual
    position of these elements in output array*/
    for (i=1; i<k+1; i++)
        C[i] = C[i] + C[i-1];
 
    //Creating Output array from C[i]
    //and decrementing value of C[i].
    for (j=n-1; j>=0; j--)
    {
        B[C[A[j]]-1] = A[j];
        C[A[j]] = C[A[j]] - 1;
    }
 
    //Printing sorted array
    printf("The Sorted array is : ");
    for (i=0; i<n; i++)
        printf("%d ", B[i]);
}
 
/*  The main() begins  */
int main()
{
    int n, max = 0,i;
    printf("Enter the number of input : ");
    scanf("%d", &n);
    int A[n];
    printf("\nEnter the elements to be sorted :\n");
    /*Storing element in a array.
     And finding max of elements to set range
     of counting array C[]*/
    for (i=0; i<n; i++)
    {
        scanf("%d", &A[i]);
        if (A[i] > max) {
            max= A[i];
        }
    }
    //calling counting-sort function
    counting_sort(A, max, n);
    printf("\n");
    return 0;
}
Counting Sort is one of the most efficient and a stable algorithm for sorting. It is simple to understand and easy to implement. A good programmer must know this linear sorting algorithm. This is also a hot topic in many beginner and algorithm based interviews.
Some other Linear Sorting Algorithms are: Bucket Sort and Radix Sort.(Will be discussed in future posts)
Radix Sort can handle larger keys more efficiently as compare to Counting Sort.
If You Enjoyed This, Take 5 Seconds To Share It

0 Questions:

Post a Comment