Back to Course

Data Structures and Algorithms with C++

0% Complete
0/0 Steps

Counting sort is an algorithm used to sort an array of elements. It is an algorithm that is efficient in terms of time and space and is often used in situations where the range of elements is known. Counting sort works by counting the occurrences of each element in the array and then uses this information to create a sorted output array. This article will cover how the algorithm works, its time complexity, and its space complexity. It will also provide examples of C++ code for each topic.

How the Algorithm Works

Counting sort is a non-comparative sorting algorithm which means that it does not compare the elements to each other. Instead, it uses the counts of each element to construct a sorted output array. The basic steps of the algorithm are as follows:

  1. Calculate the frequency of each element in the input array.
  2. Create an array (the output array) with the size equal to the number of unique elements in the input array.
  3. Initialize the output array with all zeroes.
  4. Use the frequency of each element to fill the output array.

The following example will illustrate how the algorithm works. Consider the following array of elements: [3, 4, 1, 5, 2].

First, we calculate the frequency of each element in the input array. The frequencies are as follows:

Element : Frequency

  • 3 : 1
  • 4 : 1
  • 1 : 1
  • 5 : 1
  • 2 : 1

Next, we create an output array with the size equal to the number of unique elements in the input array, which in this case is 5. The output array is initialized with all zeroes.

Finally, we use the frequency of each element to fill the output array. We start by placing a 3 in the first position of the output array since its frequency is 1. We then place a 4 in the second position of the output array since its frequency is also 1. We continue in this manner until the output array is filled.

Output array: [3, 4, 1, 5, 2]

Time Complexity

The time complexity of counting sort is linear in the worst case, which means that the time taken to sort an array is directly proportional to its size. The best and average time complexities of counting sort are also linear.

The time complexity of the algorithm can be expressed as follows:

Time complexity: O(n + k)

Where n is the size of the input array and k is the number of unique elements in the array.

Space Complexity

The space complexity of counting sort is also linear, which means that the space taken to sort an array is directly proportional to its size. The space complexity of the algorithm can be expressed as follows:

Space complexity: O(n + k)

Where n is the size of the input array and k is the number of unique elements in the array.

C++ Code

The following C++ code implements the counting sort algorithm.

//Function to sort an array using counting sort 
void countingSort(int arr[], int n, int k) 
{ 
    // Create an output array and initialize it with all zeroes 
    int output[n]; 
    for(int i=0; i < n; i++) 
        output[i] = 0; 
  
    // Create an array to store the count of each element 
    int count[k]; 
    for(int i=0; i < k; i++) 
        count[i] = 0; 
  
    // Store the count of each element 
    for(int i=0; i < n; i++) 
        count[arr[i]]++; 
  
    // Store the cummulative count of each array 
    for(int i=1; i < k; i++) 
        count[i] += count[i-1]; 
  
    // Find the index of each element of the original array in count array 
    // place the elements in output array 
    for(int i=n-1; i >= 0; i--) 
    { 
        output[count[arr[i]]-1] = arr[i]; 
        count[arr[i]]--; 
    } 
  
    // Copy the sorted elements into original array 
    for(int i=0; i < n; i++) 
        arr[i] = output[i]; 
} 

Conclusion

Counting sort is a non-comparative sorting algorithm which is efficient in terms of time and space. It is often used in situations where the range of elements is known. The basic steps of the algorithm are as follows: calculating the frequency of each element in the input array, creating an array with the size equal to the number of unique elements in the input array, initializing the output array with all zeroes, and using the frequency of each element to fill the output array. The time complexity of counting sort is linear in the worst case and its space complexity is also linear.

Exercises

Write a C++ program to implement counting sort.

#include<iostream> 
  
//Function to sort an array using counting sort 
void countingSort(int arr[], int n, int k) 
{ 
    // Create an output array and initialize it with all zeroes 
    int output[n]; 
    for(int i=0; i < n; i++) 
        output[i] = 0; 
  
    // Create an array to store the count of each element 
    int count[k]; 
    for(int i=0; i < k; i++) 
        count[i] = 0; 
  
    // Store the count of each element 
    for(int i=0; i < n; i++) 
        count[arr[i]]++; 
  
    // Store the cummulative count of each array 
    for(int i=1; i < k; i++) 
        count[i] += count[i-1]; 
  
    // Find the index of each element of the original array in count array 
    // place the elements in output array 
    for(int i=n-1; i >= 0; i--) 
    { 
        output[count[arr[i]]-1] = arr[i]; 
        count[arr[i]]--; 
    } 
  
    // Copy the sorted elements into original array 
    for(int i=0; i < n; i++) 
        arr[i] = output[i]; 
} 
  
// Function to print the array 
void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; i++) 
        std::cout << arr[i] << " "; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {3, 4, 1, 5, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 5; 
  
    countingSort(arr, n, k); 
  
    std::cout << "Sorted array is: "; 
    printArray(arr, n); 
    return 0; 
} 

Write a C++ program to find the time complexity of counting sort.

#include<iostream> 
#include<chrono> 
  
//Function to sort an array using counting sort 
void countingSort(int arr[], int n, int k) 
{ 
    // Create an output array and initialize it with all zeroes 
    int output[n]; 
    for(int i=0; i < n; i++) 
        output[i] = 0; 
  
    // Create an array to store the count of each element 
    int count[k]; 
    for(int i=0; i < k; i++) 
        count[i] = 0; 
  
    // Store the count of each element 
    for(int i=0; i < n; i++) 
        count[arr[i]]++; 
  
    // Store the cummulative count of each array 
    for(int i=1; i < k; i++) 
        count[i] += count[i-1]; 
  
    // Find the index of each element of the original array in count array 
    // place the elements in output array 
    for(int i=n-1; i >= 0; i--) 
    { 
        output[count[arr[i]]-1] = arr[i]; 
        count[arr[i]]--; 
    } 
  
    // Copy the sorted elements into original array 
    for(int i=0; i < n; i++) 
        arr[i] = output[i]; 
} 
  
// Function to calculate the time complexity of counting sort 
void timeComplexity(int arr[], int n, int k) 
{ 
    // Start the timer 
    auto start = std::chrono::high_resolution_clock::now(); 
  
    // Call the sorting function 
    countingSort(arr, n, k); 
  
    // Stop the timer 
    auto end = std::chrono::high_resolution_clock::now(); 
  
    // Calculate the time taken 
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start); 
  
    // Print the time taken 
    std::cout << "Time taken: " << duration.count() << " microseconds" << std::endl; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {3, 4, 1, 5, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 5; 
  
    timeComplexity(arr, n, k); 
    return 0; 
} 

Write a C++ program to find the space complexity of counting sort.

#include<iostream> 
  
//Function to sort an array using counting sort 
void countingSort(int arr[], int n, int k) 
{ 
    // Create an output array and initialize it with all zeroes 
    int output[n]; 
    for(int i=0; i < n; i++) 
        output[i] = 0; 
  
    // Create an array to store the count of each element 
    int count[k]; 
    for(int i=0; i < k; i++) 
        count[i] = 0; 
  
    // Store the count of each element 
    for(int i=0; i < n; i++) 
        count[arr[i]]++; 
  
    // Store the cummulative count of each array 
    for(int i=1; i < k; i++) 
        count[i] += count[i-1]; 
  
    // Find the index of each element of the original array in count array 
    // place the elements in output array 
    for(int i=n-1; i >= 0; i--) 
    { 
        output[count[arr[i]]-1] = arr[i]; 
        count[arr[i]]--; 
    } 
  
    // Copy the sorted elements into original array 
    for(int i=0; i < n; i++) 
        arr[i] = output[i]; 
} 
  
// Function to calculate the space complexity of counting sort 
void spaceComplexity(int arr[], int n, int k) 
{ 
    // Calculate the space taken 
    int space = (n + k) * sizeof(int); 
  
    // Print the space taken 
    std::cout << "Space taken: " << space << " bytes" << std::endl; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {3, 4, 1, 5, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 5; 
  
    spaceComplexity(arr, n, k); 
    return 0; 
} 

Write a C++ program to demonstrate the working of counting sort.

#include<iostream> 
  
//Function to sort an array using counting sort 
void countingSort(int arr[], int n, int k) 
{ 
    // Create an output array and initialize it with all zeroes 
    int output[n]; 
    for(int i=0; i < n; i++) 
        output[i] = 0; 
  
    // Create an array to store the count of each element 
    int count[k]; 
    for(int i=0; i < k; i++) 
        count[i] = 0; 
  
    // Store the count of each element 
    for(int i=0; i < n; i++) 
        count[arr[i]]++; 
  
    // Store the cummulative count of each array 
    for(int i=1; i < k; i++) 
        count[i] += count[i-1]; 
  
    // Find the index of each element of the original array in count array 
    // place the elements in output array 
    for(int i=n-1; i >= 0; i--) 
    { 
        output[count[arr[i]]-1] = arr[i]; 
        count[arr[i]]--; 
    } 
  
    // Copy the sorted elements into original array 
    for(int i=0; i < n; i++) 
        arr[i] = output[i]; 
} 
  
// Function to print the array 
void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; i++) 
        std::cout << arr[i] << " "; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {3, 4, 1, 5, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 5; 
  
    std::cout << "Input array: "; 
    printArray(arr, n); 
  
    countingSort(arr, n, k); 
  
    std::cout << "\nSorted array is: "; 
    printArray(arr, n); 
    return 0; 
} 

Write a C++ program to find the frequency of each element in an array.

#include<iostream> 
  
// Function to calculate the frequency of each element in an array 
void frequency(int arr[], int n) 
{ 
    // Create an array to store the count of each element 
    int count[n]; 
    for(int i=0; i < n; i++) 
        count[i] = 0; 
  
    // Store the count of each element 
    for(int i=0; i < n; i++) 
        count[arr[i]]++; 
  
    // Print the frequency of each element 
    for (int i = 0; i < n; i++) 
        std::cout << arr[i] << " " << count[arr[i]] << std::endl; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = {3, 4, 1, 5, 2, 3, 4, 1, 5, 2, 1, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    frequency(arr, n); 
    return 0; 
}