Counting Sort is a non-comparison-based sorting algorithm that works particularly well when you have a limited range of input values. It counts the number of occurrences of each element and uses this information to place each element in its correct sorted position.
Here’s how Counting Sort works,
Step 1: Find the range of input values (minimum and maximum values) to determine the range of the count array.
Step 2: Create a count array with a size equal to the range of input values and initialize all the counts to zero.
Step 3: Iterate through the input array and increment the count for each element in the count array. For each input element, the count array keeps track of how many times that element appears.
Step 4: Calculate the cumulative counts. For each index in the count array, add the count at that index to the count of the previous index. This step helps in determining the correct positions of elements with equal values.
Step 5: Create a temporary array of the same size as the input array to store the sorted elements.
Step 6: Iterate through the input array from right to left (to preserve stability), look up the count of the element in the count array, and use the cumulative count to find its correct sorted position in the temporary array. Decrease the cumulative count by 1 after each placement.
Step 7: Copy the elements from the temporary array back into the original input array, completing the sorting process.
Step 1: Find the range of input values (minimum and maximum values) to determine the range of the count array.
Step 2: Create a count array with a size equal to the range of input values and initialize all the counts to zero.
Step 3: Iterate through the input array and increment the count for each element in the count array. For each input element, the count array keeps track of how many times that element appears.
Step 4: Calculate the cumulative counts. For each index in the count array, add the count at that index to the count of the previous index. This step helps in determining the correct positions of elements with equal values.
Step 5: Create a temporary array of the same size as the input array to store the sorted elements.
Step 6: Iterate through the input array from right to left (to preserve stability), look up the count of the element in the count array, and use the cumulative count to find its correct sorted position in the temporary array. Decrease the cumulative count by 1 after each placement.
Step 7: Copy the elements from the temporary array back into the original input array, completing the sorting process.
countingSort(array, n)
// 'n' is the size of array
max = find maximum element in the given array
create count array with size maximum + 1
Initialize count array with all 0's
for i = 0 to n
find the count of every unique element and
store that count at ith position in the count array
for j = 1 to max
Now, find the cumulative
sum and store it in count array
for i = n to 1
Restore the array elements
Decrease the count of every restored element by 1
end countingSort
Example:
Suppose you have the following array of non-negative integers to sort:
Original array: [4, 2, 2, 8, 3, 3, 1]
1. Find the range of values: The minimum value is 1, and the maximum value is 8. So, the range of values is 1 to 8.
2. Create a count array with a size of 8 (to cover the range of values) and initialize all counts to 0:
Count array: [0, 0, 0, 0, 0, 0, 0, 0]
3. Count the occurrences of each element in the original array:
Count array: [1, 2, 2, 2, 1, 0, 0, 1]
4. Calculate cumulative counts:
Count array: [1, 3, 5, 7, 8, 8, 8, 9]
5. Create a temporary array of the same size as the input array:
Temporary array: [0, 0, 0, 0, 0, 0, 0, 0]
6. Iterate through the original array from right to left:For the last element, which is 1, look up its count (1) and its cumulative count (8). Place it at index 8 in the temporary array and decrement the cumulative count by 1.
Continue this process for the remaining elements, placing them in their correct sorted positions in the temporary array.
Temporary array: [1, 2, 2, 3, 3, 4, 8, 0]
7. Copy the elements from the temporary array back into the original array: Original array: [1, 2, 2, 3, 3, 4, 8, 0]
Suppose you have the following array of non-negative integers to sort:
Original array: [4, 2, 2, 8, 3, 3, 1]
1. Find the range of values: The minimum value is 1, and the maximum value is 8. So, the range of values is 1 to 8.
2. Create a count array with a size of 8 (to cover the range of values) and initialize all counts to 0:
Count array: [0, 0, 0, 0, 0, 0, 0, 0]
3. Count the occurrences of each element in the original array:
Count array: [1, 2, 2, 2, 1, 0, 0, 1]
4. Calculate cumulative counts:
Count array: [1, 3, 5, 7, 8, 8, 8, 9]
5. Create a temporary array of the same size as the input array:
Temporary array: [0, 0, 0, 0, 0, 0, 0, 0]
6. Iterate through the original array from right to left:
7. Copy the elements from the temporary array back into the original array: Original array: [1, 2, 2, 3, 3, 4, 8, 0]
Advantages Of Counting Sort Alogirithm
Counting Sort is highly efficient when the range of input values is limited, and the values are relatively small. It has a linear time complexity, O(n + k), where “n” is the number of elements to be sorted and “k” is the range of input values. This makes it significantly faster than comparison-based sorting algorithms like Quick Sort or Merge Sort for such cases.
Counting Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements. This is crucial when you want to sort data by multiple criteria or when maintaining the original order of equivalent values is important.
While Counting Sort typically uses extra space for the count array and the temporary array, it can be modified to perform in-place sorting. This can be advantageous in situations where memory usage is a critical concern.
Counting Sort is a deterministic algorithm, meaning it will always produce the same output for a given input, making it suitable for applications that require predictable results.
Unlike many sorting algorithms that rely on comparisons, Counting Sort does not involve element comparisons, which can be computationally expensive. This characteristic can make it faster than comparison-based sorting algorithms in certain scenarios.
