Back to Course

Data Structures and Algorithms with C++

0% Complete
0/0 Steps
  1. Introduction to Data Structures and Algorithms
    Overview of Data Structures and Algorithms with C++
  2. Importance of Data Structures and Algorithms in Programming with C++
  3. How to Choose the Right Data Structure or Algorithm for a given Problem with C++
  4. Basic C++ Concepts Review
    Variables and Data Types in C++
  5. Control Flow Statements in C++
  6. Classes and Objects in C++
  7. Methods and Constructors in C++
  8. Basic Input and Output in C++
  9. Data Structures
    Arrays in C++
  10. Stacks and Queues in C++
  11. Linked Lists in C++
  12. Hash Tables in C++
  13. Trees in C++
  14. Types of Trees
    Binary Search Trees in C++
  15. Cartesian Trees in C++
  16. B-Trees in C++
  17. Red-Black Trees in C++
  18. Splay Trees in C++
  19. AVL Trees in C++
  20. KD Trees in C++
  21. Min Heap in C++
  22. Max Heap in C++
  23. Trie Trees in C++
  24. Suffix Trees in C++
  25. Sorting Algorithms
    Quicksort in C++
  26. Mergesort in C++
  27. Timsort in C++
  28. Heapsort in C++
  29. Bubble Sort in C++
  30. Insertion Sort in C++
  31. Selection Sort in C++
  32. Tree Sort in C++
  33. Shell Sort in C++
  34. Bucket Sort in C++
  35. Radix Sort in C++
  36. Counting Sort in C++
  37. Cubesort in C++
  38. Searching Algorithms
    Linear Search in C++
  39. Binary Search in C++
  40. Graphing Algorithms
    Breadth First Search (BFS) in C++
  41. Depth First Search (DFS) in C++
  42. Dijkstra’s Algorithm in C++
  43. Algorithm Design Techniques
    Greedy Algorithms in C++
  44. Dynamic Programming in C++
  45. Divide and Conquer in C++
  46. Backtracking in C++
  47. Randomized Algorithms in C++
  48. Conclusion
    Recap of DSA with C++

Participants 445

Show more

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; 
}