Counting Sort Analysis

Hi everyone, inside this article we will see the concept about Counting Sort Analysis.

Counting Sort is an efficient non-comparison based sorting algorithm used to sort elements in a given array or list. Unlike other sorting algorithms like Bubble Sort, Quick Sort or Merge Sort which are comparison based, Counting Sort is based on the frequency of elements in the input array.

How Algorithm of Count Sort works?

The basic steps of the Counting Sort algorithm are as follows:

1. Find the maximum element in the input array.
2. Create an array to store the count of each element in the input array.
3. Traverse the input array and count the frequency of each element.
4. Modify the count array to contain the actual position of each element in the output array.
5. Traverse the input array again and place each element in the correct position in the output array based on the count array.

Here is the pseudocode for Counting Sort:

counting_sort(array, size)
    max_element = find_max_element(array, size)
    count_array = new Array(max_element + 1)
    output_array = new Array(size)
    
    for i in range(size):
        count_array[array[i]] += 1
    
    for i in range(1, max_element + 1):
        count_array[i] += count_array[i - 1]
        
    for i in range(size - 1, -1, -1):
        output_array[count_array[array[i]] - 1] = array[i]
        count_array[array[i]] -= 1
    
    for i in range(size):
        array[i] = output_array[i]

The time complexity of Counting Sort is O(n + k) where n is the size of the input array and k is the maximum value in the array. This makes Counting Sort efficient when the range of values in the input array is small compared to the size of the array. However, if the range of values is very large, then the memory required for the count array will also be large and Counting Sort may not be practical.

A Basic Example of Counting Sort with Steps

Here’s an example of how Counting Sort works:

Input: [3, 1, 6, 2, 3, 1, 3] Output: [1, 1, 2, 3, 3, 3, 6]

1. Create an array of counts with size 6 (maximum element value is 6, minimum element value is 1). counts = [0, 0, 0, 0, 0, 0]
2. Initialize all elements of the counts array to zero. counts = [0, 0, 0, 0, 0, 0]
3. Traverse the input array and increment the count of the corresponding element in the counts array. counts = [0, 2, 1, 3, 0, 1]
4. Modify the counts array such that each element at index i contains the sum of counts of elements less than or equal to i. counts = [0, 2, 3, 6, 6, 7]
5. Create a temporary output array of the same size as the input array. output = [0, 0, 0, 0, 0, 0, 0]
6. Traverse the input array from right to left. For each element, use the counts array to determine its position in the output array, place the element in that position, and decrement the count of the corresponding element in the counts array. counts = [0, 2, 2, 5, 5, 7] output = [0, 0, 0, 0, 0, 0, 0] output[6] = 6, counts[6] = 0 output[5] = 3, counts[3] = 2 output[4] = 3, counts[3] = 1 output[3] = 3, counts[3] = 0 output[2] = 2, counts[2] = 2 output[1] = 1, counts[1] = 1 output[0] = 1, counts[1] = 0
7. The output array is now sorted. output = [1, 1, 2, 3, 3, 3, 6]

Example Code

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int> &arr, int range)
{
  vector<int> count(range + 1, 0);
  vector<int> output(arr.size());

  for (int i = 0; i < arr.size(); i++)
  {
    count[arr[i]]++;
  }

  for (int i = 1; i <= range; i++)
  {
    count[i] += count[i - 1];
  }

  for (int i = arr.size() - 1; i >= 0; i--)
  {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }

  arr = output;
}

int main()
{
  vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
  int range = 8;

  countingSort(arr, range);

  for (int i = 0; i < arr.size(); i++)
  {
    cout << arr[i] << " ";
  }

  return 0;
}

The above program will output:

1 2 2 3 3 4 8 

Complexity Analysis of Counting Sort

The time complexity of Counting Sort is O(n+k), where n is the number of elements in the input array and k is the range of input. The space complexity of Counting Sort is also O(n+k).

Counting Sort has a linear time complexity which makes it very efficient for sorting large datasets. However, it requires additional memory to store the count array, which can make it less efficient in situations where memory is limited.

Counting Sort is particularly useful when the input array contains a small range of values. For example, if the input array contains integers in the range 1 to 10,000, then Counting Sort would be very efficient.

In situations where the input array contains a large range of values, Counting Sort may not be the best choice. In such cases, other sorting algorithms such as Merge Sort or Quick Sort may be more suitable.

Where is the Counting sort algorithm used?

Counting sort algorithm is often used in situations where we need to sort an array of non-negative integers in a small range. It has a linear time complexity, which means it can be very efficient for sorting such arrays. Some of the specific applications of counting sort include:

1. Sorting grades of students in a class.
2. Sorting ages of people in a population.
3. Sorting daily sales figures of a retail store.
4. DNA sequencing.
5. Image processing.

Advantages:

• Counting sort has a linear time complexity, making it very efficient for large datasets.
• It is a stable sort, meaning that it maintains the relative order of equal elements in the input array.
• Counting sort is very useful when the range of input elements is small, and the number of elements is significantly larger than the range.

Disadvantages:

• Counting sort can only be used when the range of input elements is known and relatively small. If the range is large, then the space required for the count array will also be large.
• If the range of input elements is not an integer range, then counting sort cannot be used.
• Counting sort is not an in-place sorting algorithm, meaning that it requires additional memory space to store the count array and the output array.

We hope this article helped you to understand Counting Sort Analysis in a very detailed way.

Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.

If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.