Counting Sort in C++
In C++, a basic sorting technique called counting sort is used to quickly sort a set of integers or objects having integer keys. Counting sort doesn't depend on comparisons between items, compared to specific other sorting algorithms. Instead, it counts how many times there is every unique element (or key) and utilizes this data to rank the elements according to that count. When working with a small number of input values, counting sort is very effective.
Counting how many times there are of each unique element as it continuously goes through the input data is how the method works. This count information is then used to sort each element into its location. Since counting sort maintains the relative order of equal elements in the sorted output, it is a stable sorting algorithm. Even though it is quite effective in some situations, there may be better options for sorting huge datasets or when there are a lot more input values than there are items that need to be sorted. Even so, it is a helpful tool for sorting algorithms since it often has linear time complexity.
Working of Counting Sort
When your input value range has limitations, the effective sorting technique known as counting sort performs excellently. To sort the items in the input data, it counts the instances of each unique element and uses the count information. This is a brief description of how C++'s Counting Sort functions:
1. Determine the Range:
To use Counting Sort, you must first determine the range of input values (i.e., the lowest and maximum values). This range determines the sizes of the counting array.
2. Counting Phase:
- Assign the size of the counting array to the input value range.
- Set the count array's elements all to zero at first.
- In the counting array, increase the relevant index for each element as you iterate through the incoming data. To increase the counting array at index 3, for instance, if an input element is 3.
- The number of instances of each unique element in the input data is stored in the counting array following this counting step.
3. Cumulative Counting:
To express cumulative counts, modify the counting array. In the updated counting array, the count of items less than or equal to each element's corresponding index will now be present in each element. The elements' locations in the sorted output are determined in part by this phase.
4. Sorting Phase:
- Make an output array the same size as the data that was provided.
- To ensure stability, go through the input data in reverse order. For each element, use the cumulative counting array to determine its position in the sorted output.
- The element's value in the counting array's cumulative count is decreased.
- Insert the element at the specified location in the output array.
5. Final Output:
The elements in the output array are now ordered ascending.
How Counting Sort is Different from Others
There are multiple key ways in which Counting Sort is different from other sorting algorithms, including QuickSort, MergeSort, and HeapSort:
- Not Comparison-Based: The sorting algorithm known as counting sort is not dependent on comparisons. It determines the order of components without comparing them to each other. To arrange the items in their sorted places, it instead counts the instances of each unique element. Because of this, counting and sorting integers or objects with integer keys is highly effective.
- Range Dependence: When working with a small number of input values, counting sort works well. Counting sort may become less useful if the range is much greater than the number of elements that need to be sorted because of the counting array's memory needs.
- Non-Comparison Sorting: The counting sort is a sorting algorithm that falls within the non-comparison sorting category. Other non-comparison sorts are Bucket Sort and Radix Sort, each having unique properties and application cases.
- Linear Time Complexity: The counting sort has a linear time complexity of O(n + k), where k is the input value range, and n is the number of elements that need to be sorted. One of the quickest sorting algorithms for a given range of input values is Counting sort because of its linear time complexity. Comparatively speaking, comparison-based algorithms frequently have an immediate complexity of at least O(n*log(n)).
- Consistency: Counting Since sort maintains the relative order of equal elements in the sorted output, it is a stable sorting algorithm. The stability of other sorting algorithms is contingent upon how they are implemented.
Example code:
#include<iostream>
using namespace std;
void countSort(int arr[], int size) {
// Determine the range and initialize the counting and output arrays
int output[size];
int count[size];
int max = arr[0];
//Finding the largest element in the given array
for( int i = 1; i<size ;i++ ){
if(arr[i] > max)
max = arr[i];
}
//Initialize the count array with all zeros
for (int i = 0; i <= max; ++i) {
count[i] = 0;
}
//Store the count of each element
for(int i = 0; i < size; i++) {
count[arr[i] ]++;
}
//Store the cumulative count of each element
for(int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
//Calculate the count array's index for every component in the original array.
//and place the elements in the output array
for(int i=size-1;i>=0;i--){
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
//Copy the sorted elements from the output array back into the original array
for(int i = 0; i < size; i++) {
arr[i] = output[i];
}
}
//Function to print an array
void printArray(int arr[], int size) {
for(int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main(){
int arr[] = {7, 3, 2, 8, 1, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// Perform Counting Sort
countSort(arr, n);
// Print the sorted array
printArray(arr, n);
return 0;
}
Output:
![Counting Sort in C++](https://static.tutorialandexample.com/cpp/counting-sort-in-cpp1.png)
Explanation:
This code displays a non-comparison-based sorting method called the Counting Sort algorithm in C++. When sorting an integer collection inside a narrow range of values, counting sort is an effective method. Let's take a quick look at this code's operation.
The sorting is done using the countSort Function. To generate an output array and a counting array, it first determines the range of values in the input array. While the sorted elements are stored in the output array, the counting array counts the instances of each unique element.
The most significant member in the input array is then located by the code, which aids in defining the range. All the counting array's elements are set to zero as it initializes. Then, it counts the instances of each element as it scans the input array, putting the numbers in the counting array.
The algorithm then modifies the counting array to reflect the cumulative counts. In the sorted output, this step ensures that every element knows its location.
The elements are sorted in the following loop by assigning them to the appropriate opportunities in the output array according to the cumulative count. To keep the algorithm stable and the order of equal items intact, the elements are sorted, starting with the last and working their way up.
After sorting the elements, the method returns the original input array to its original state. After sorting, the array is prepared for display.
Conclusion
In conclusion, this C++ code's Counting Sort algorithm is a helpful sorting method, particularly when managing an integer collection with a limited number of values. In addition to having linear immediate complexity, it has several other benefits. Counting sort is a stable sorting technique that maintains the relative order of equal items by effectively counting the instances of each unique element and sorting the input array based on these counts.
This code displays every step of the Counting Sort process, from setting up the counting array to changing cumulative counts and sorting the components into the correct locations. An array that has been sorted is the end product, which has several uses.
Even though the Counting sort is successful in specific scenarios, it is important to remember that its effectiveness depends on the range of values. It could be less effective for sorting large datasets when the range of values is significantly more extensive than the total number of objects to be sorted. Still, it's a helpful addition to the toolbox of sorting algorithms, offering a new and practical approach to sorting in C++.