Counting Sort
Time Complexity
| Best | Average | Worst |
|---|---|---|
| Ω(n+k) | Θ(n+k) | Θ(n+k) |
Space Complexity
| Worst |
|---|
| O(k) |
Overview
Counting Sort is a method of arranging elements in a list that is especially effective when dealing with an expected range of values. It can be used for input of positive integers only. The technique involves finding the occurrences of each unique element in the input list and using this information to determine their proper order in the sorted output. It's generally difficult to understand in theory but is incredibly easy to understand visually (the animation helps a lot in that regard).
Now to the step by step explanation for the animation input list [7, 3, 7, 1, 4, 3, 3]:
- Identify the range of input values To begin, we need to find the smallest and largest values in the input list to determine the range of values.
Minimum value: 1
Maximum value: 7
- Prepare a counting array We create a counting array with a size corresponding to the range of values. In this case, it will be an array of size 7 (since the maximum value is 7).
So the initial counting array is [0, 0, 0, 0, 0, 0, 0].
- Count occurrences Next, we count the occurrences of each element as we scan through the input list and increment the count of each element in the counting array.
Input list: [7, 3, 7, 1, 4, 3, 3]
After counting: [1, 0, 3, 1, 0, 0, 2]
Explanation:
- The number 1 appears once in the input list, so the counting array at index 1 is incremented to 1.
- The number 3 appears three times in the input list, so the counting array at index 3 is incremented to 3.
- The number 4 appears once, so index 4 is set to 1.
- Similarly, the number 7 appears twice in the input list, so the counting array at index 7 is incremented to 2.
-
Update the counting array We modify the counting array to reflect the correct positions of elements in the sorted output. Each element in the counting array will represent the last index of that element in the sorted list.
-
Generate the sorted output list We traverse the input list again and use the modified counting array to place each element in its correct position in the sorted output list.
-
The Sorting is finally complete.
In conclusion, Counting Sort is an efficient algorithm with a time complexity of O(n+k), where n is the number of elements in the input list, and k is the range of input values. However, it requires additional space for the counting array, making it less practical for large ranges of input values. And it can only be used for data sets with a known length.
Code
def counting_sort(input_list):
max_val = max(input_list)
min_val = min(input_list)
range_values = max_val - min_val + 1
counting_array = [0] * range_values
for num in input_list:
counting_array[num - min_val] += 1
sorted_output = []
for i in range(range_values):
while counting_array[i] > 0:
sorted_output.append(i + min_val)
counting_array[i] -= 1
return sorted_output
# Example usage:
input_lst = [7, 3, 7, 1, 4, 3, 3]
sorted_lst = counting_sort(input_lst)
print(sorted_lst) # Output: [1, 3, 3, 3, 4, 7, 7]
function countingSort(arr) {
const maxVal = Math.max(...arr);
const minVal = Math.min(...arr);
const rangeValues = maxVal - minVal + 1;
const countingArray = new Array(rangeValues).fill(0);
for (const num of arr) {
countingArray[num - minVal]++;
}
const sortedOutput = [];
for (let i = 0; i < rangeValues; i++) {
while (countingArray[i] > 0) {
sortedOutput.push(i + minVal);
countingArray[i]--;
}
}
return sortedOutput;
}
// Example usage:
const inputLst = [7, 3, 7, 1, 4, 3, 3];
const sortedLst = countingSort(inputLst);
console.log(sortedLst); // Output: [1, 3, 3, 3, 4, 7, 7]
import java.util.Arrays;
public class CountingSort {
public static int[] countingSort(int[] arr) {
int maxVal = Arrays.stream(arr).max().getAsInt();
int minVal = Arrays.stream(arr).min().getAsInt();
int rangeValues = maxVal - minVal + 1;
int[] countingArray = new int[rangeValues];
for (int num : arr) {
countingArray[num - minVal]++;
}
int[] sortedOutput = new int[arr.length];
int index = 0;
for (int i = 0; i < rangeValues; i++) {
while (countingArray[i] > 0) {
sortedOutput[index] = i + minVal;
countingArray[i]--;
index++;
}
}
return sortedOutput;
}
// Example usage:
public static void main(String[] args) {
int[] inputArr = {7, 3, 7, 1, 4, 3, 3};
int[] sortedArr = countingSort(inputArr);
System.out.println("Sorted Output: " + Arrays.toString(sortedArr));
}
}
#include <stdio.h>
void counting_sort(int arr[], int n) {
int max_val = arr[0];
int min_val = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
}
if (arr[i] < min_val) {
min_val = arr[i];
}
}
int range_values = max_val - min_val + 1;
int counting_array[range_values];
for (int i = 0; i < range_values; i++) {
counting_array[i] = 0;
}
for (int i = 0; i < n; i++) {
counting_array[arr[i] - min_val]++;
}
int sorted_output[n];
int index = 0;
for (int i = 0; i < range_values; i++) {
while (counting_array[i] > 0) {
sorted_output[index] = i + min_val;
counting_array[i]--;
index++;
}
}
for (int i = 0; i < n; i++) {
arr[i] = sorted_output[i];
}
}
// Example usage:
int main() {
int input_lst[] = {7, 3, 7, 1, 4, 3, 3};
int n = sizeof(input_lst) / sizeof(input_lst[0]);
counting_sort(input_lst, n);
printf("Sorted Output: ");
for (int i = 0; i < n; i++) {
printf("%d ", input_lst[i]);
}
printf("\n");
return 0;
}
function countingSort($arr) {
$maxVal = max($arr);
$minVal = min($arr);
$rangeValues = $maxVal - $minVal + 1;
$countingArray = array_fill(0, $rangeValues, 0);
foreach ($arr as $num) {
$countingArray[$num - $minVal]++;
}
$sortedOutput = array();
foreach ($countingArray as $i => $count) {
while ($count > 0) {
$sortedOutput[] = $i + $minVal;
$count--;
}
}
return $sortedOutput;
}
// Example usage:
$inputLst = [7, 3, 7, 1, 4, 3, 3];
$sortedLst = countingSort($inputLst);
print_r($sortedLst); // Output: Array ( [0] => 1 [1] => 3 [2] => 3 [3] => 3 [4] => 4 [5] => 7 [6] => 7 )