Counting Sort is a sorting algorithm that works on integer inputs with a specific range. It is an efficient algorithm that sorts the elements based on their keys by counting the number of occurrences of each key. The algorithm assumes that the input consists of integers within a known range.
Here's how the Counting Sort algorithm works:
Find the minimum and maximum values in the input array and determine the range of input values.
Create an auxiliary array called "count" with a length equal to the range of input values. Initialize all elements of the count array to 0.
Iterate through the input array and count the occurrences of each value by incrementing the corresponding index in the count array.
Modify the count array such that each element at index 'i' stores the sum of the previous counts.
This step helps determine the correct positions of each element in the sorted output array.
Create an output array with the same length as the input array.
Iterate through the input array in reverse order. For each element, use its value as an index in the count array to determine its position in the output array. Decrement the count for that value by 1.
Place the element in the determined position in the output array.
Once all the elements are placed in the output array, it will contain the sorted order of the input array based on the keys.
Counting Sort has a time complexity of O(n + k), where 'n' is the number of elements in the input array and 'k' is the range of input values. It is considered efficient when the range of input values is small compared to the number of elements.
It is important to note that Counting Sort is not suitable for inputs with negative values or floating-point numbers since it relies on using array indices for counting and sorting.
Stability: Counting Sort is a stable sorting algorithm, meaning that it preserves the relative order of elements with equal keys. If two elements have the same key, the element that appears earlier in the input array will also appear earlier in the sorted output array.
Range of Input Values: Counting Sort is particularly efficient when the range of input values (k) is relatively small compared to the number of elements (n) in the input array. In such cases, the time complexity of the algorithm is effectively linear, making it faster than comparison-based sorting algorithms like QuickSort or MergeSort.
Auxiliary Space: Counting Sort requires additional space for the auxiliary count array, which has a size equal to the range of input values. The overall space complexity of Counting Sort is O(n + k), where n is the number of elements and k is the range of input values.
Limitations: While Counting Sort has its advantages for certain scenarios, it also has limitations. It becomes impractical when the range of input values is significantly larger than the number of elements, as it would require a large amount of memory for the auxiliary count array. Additionally, Counting Sort cannot be directly applied to inputs with negative values or floating-point numbers, as it relies on using array indices for counting and sorting.
Adaptations: There are variations of Counting Sort that address some of its limitations. For example, if negative values are present in the input, we can shift the range to make all values non-negative and adjust the sorting accordingly. Another variant, called Radix Sort, extends Counting Sort to handle inputs with multiple keys or digits.
Overall, Counting Sort is a simple and efficient sorting algorithm that performs well in scenarios where the range of input values is relatively small. Its linear time complexity makes it a useful choice when applied to appropriate situations, such as sorting integers within a known range.
Input: A list of unsorted data: 2 5 6 2 3 10 3 6 7 8 Output: Array before Sorting: 2 5 6 2 3 10 3 6 7 8 Array after Sorting: 2 2 3 3 5 6 6 7 8 10
counting sort(array, size)
Input: An array of data, and the total number in the array.
Output: The sorted Array
Begin
max = get maximum element from array.
define count array of size [max+1]
for i := 0 to max do
count[i] = 0 //set all elements in the count array to 0
done
for i := 1 to size do
increase count of each number which have found in the array
done
for i := 1 to max do
count[i] = count[i] + count[i+1] //find cumulative frequency
done
for i := size to 1 decrease by 1 do
store the number in the output array
decrease count[i]
done
return the output array
End