What is Counting Sort
Counting sort is a sorting algorithm that works by counting the number of occurrences of each unique element in a list and using that information to sort the list. Here's how it works:
- Counting: First, we create a "count" array that stores the number of occurrences of each unique element in the input list. We iterate through the input list, and for each element we encounter, we increment the corresponding count in the count array.
- Accumulation: Next, we modify the count array so that each element stores the sum of the previous counts. This means that each element in the count array represents the number of elements that are less than or equal to the corresponding element in the input list.
- Sorting: Finally, we create a new output list and iterate through the input list again. For each element, we use the count array to determine its sorted position in the output list, and then we decrement the corresponding count in the count array. This process ensures that elements with the same value are sorted in the same order as they appeared in the input list.
Who invented it?
Counting sort was first introduced by Harold Seward in 1954, but the algorithm was independently discovered by Ivan Munro and Vladimir Sukharev in the same year. Seward's paper "The Distribution Sort - A Technique for Correlating and Disseminating Data" described a variant of counting sort that was used to sort punched card data, while Munro and Sukharev's paper "Sorting and Searching" presented a more general version of the algorithm. The algorithm has since been refined and improved by many researchers, and is now widely used in various applications
Pseudocode
countingSort(list, maxVal):
// Create a count array with length maxVal+1 and initialize each element to 0
count = new Array(maxVal+1)
for i = 0 to maxVal:
count[i] = 0
// Count the number of occurrences of each element in the list
for i = 0 to length(list)-1:
count[list[i]] = count[list[i]] + 1
// Modify the count array so that each element represents the sum of the previous counts
for i = 1 to maxVal:
count[i] = count[i] + count[i-1]
// Create a new output list and sort the elements based on their counts
output = new Array(length(list))
for i = length(list)-1 down to 0:
output[count[list[i]]-1] = list[i]
count[list[i]] = count[list[i]] - 1
// Return the sorted output list
return output
In this pseudocode, list is the input list to be sorted, and maxVal is the maximum value that can appear in the input list. The algorithm first creates a count array with length maxVal+1 and initializes each element to 0. It then counts the number of occurrences of each element in the input list by iterating through the list and incrementing the corresponding count in the count array. The count array is then modified so that each element represents the sum of the previous counts, and a new output list is created. The input list is then iterated through again, and each element is placed in its sorted position in the output list based on its count. Finally, the sorted output list is returned.
Sample Code
// C++ code snippet
vector countingSort(vector list, int maxVal) {
// Create a count array with length maxVal+1 and initialize each element to 0
vector count(maxVal+1, 0);
// Count the number of occurrences of each element in the list
for (int i = 0; i < list.size(); i++) {
count[list[i]]++;
}
// Modify the count array so that each element represents the sum of the previous counts
for (int i = 1; i <= maxVal; i++) {
count[i] += count[i-1];
}
// Create a new output list and sort the elements based on their counts
vector output(list.size());
for (int i = list.size()-1; i >= 0; i--) {
output[count[list[i]]-1] = list[i];
count[list[i]]--;
}
// Return the sorted output list
return output;
}
int main() {
vector list = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int maxVal = 9;
vector sortedList = countingSort(list, maxVal);
cout << "Sorted list: ";
for (int i = 0; i < sortedList.size(); i++) {
cout << sortedList[i] << " ";
}
cout << endl;
return 0;
}
# Python code snippet
def counting_sort(lst, max_val):
# Create a count array with length max_val+1 and initialize each element to 0
count = [0] * (max_val+1)
# Count the number of occurrences of each element in the list
for num in lst:
count[num] += 1
# Modify the count array so that each element represents the sum of the previous counts
for i in range(1, max_val+1):
count[i] += count[i-1]
# Create a new output list and sort the elements based on their counts
output = [0] * len(lst)
for i in range(len(lst)-1, -1, -1):
output[count[lst[i]]-1] = lst[i]
count[lst[i]] -= 1
# Return the sorted output list
return output
# Example usage:
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
max_val = 9
sorted_lst = counting_sort(lst, max_val)
print("Sorted list:", sorted_lst)
import java.util.Arrays;
public class CountingSort {
public static int[] countingSort(int[] arr, int maxVal) {
// Create a count array with length maxVal+1 and initialize each element to 0
int[] count = new int[maxVal+1];
// Count the number of occurrences of each element in the array
for (int num : arr) {
count[num]++;
}
// Modify the count array so that each element represents the sum of the previous counts
for (int i = 1; i <= maxVal; i++) {
count[i] += count[i-1];
}
// Create a new output array and sort the elements based on their counts
int[] output = new int[arr.length];
for (int i = arr.length-1; i >= 0; i--) {
output[count[arr[i]]-1] = arr[i];
count[arr[i]]--;
}
// Return the sorted output array
return output;
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int maxVal = 9;
int[] sortedArr = countingSort(arr, maxVal);
System.out.print("Sorted array: ");
System.out.println(Arrays.toString(sortedArr));
}
}