Back to Course

0% Complete
0/0 Steps

Lesson 36 of 48
In Progress

# Counting Sort in C++

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);
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);
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);
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);
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);
frequency(arr, n);
return 0;
}