Counting Sort
Counting Sort is a non-comparison based sorting algorithm. It works by counting how many times each element appears, then reconstructing the sorted array using those counts.
Best when:
Numbers are non-negative integers.
Range (max – min) is small.
Time Complexity
O(n + k)
where k: range.
If ‘k’ (range) is small, then this algorithm is efficient.
Space Complexity
O(K)
Points to remember while using this algorithm
Elements are integers.
Values are small in range.
Examples
- Marks of students (0 to 100) (range)
- Percentages
- Sort based on Ages (0-120)
- Digits(0 – 9)
Disadvantage
Not Stable algorithm
Reasons:
- We only count frequencies.
- Then we overwrite the original array.
- We don’t remember the original order of equal elements.
- So if two elements have the same value, their relative order may change.
function countingSort(arr) {
let max = Math.max(...arr);
let count = new Array(max + 1).fill(0);
for (let x of arr) {
count[x]++;
}
let index = 0;
for (let i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index] = i;
index++;
count[i]--;
}
}
return arr;
}
let nums = [4, 2, 5, 3, 3, 2, 1, 4];
console.log(countingSort(nums));
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
for x in arr:
count[x] += 1
index = 0
for i in range(len(count)):
while count[i] > 0:
arr[index] = i
index += 1
count[i] -= 1
return arr
nums = [4, 2, 5, 3, 3, 2, 1, 4]
print(counting_sort(nums))
import java.util.*;
public class CountingSort {
public static int[] countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int[] count = new int[max + 1];
for (int x : arr) {
count[x]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
return arr;
}
public static void main(String[] args) {
int[] nums = {4, 2, 5, 3, 3, 2, 1, 4};
System.out.println(Arrays.toString(countingSort(nums)));
}
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector countingSort(vector& arr) {
int maxVal = *max_element(arr.begin(), arr.end());
vector count(maxVal + 1, 0);
for (int x : arr) {
count[x]++;
}
int index = 0;
for (int i = 0; i < count.size(); i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
return arr;
}
int main() {
vector nums = {4, 2, 5, 3, 3, 2, 1, 4};
nums = countingSort(nums);
for (int x : nums)
cout << x << " ";
}
#include <stdio.h>
void countingSort(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
int count[max + 1];
for (int i = 0; i <= max; i++)
count[i] = 0;
for (int i = 0; i < n; i++)
count[arr[i]]++;
int index = 0;
for (int i = 0; i <= max; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
int main() {
int nums[] = {4, 2, 5, 3, 3, 2, 1, 4};
int n = sizeof(nums) / sizeof(nums[0]);
countingSort(nums, n);
for (int i = 0; i < n; i++)
printf("%d ", nums[i]);
return 0;
}
using System;
using System.Linq;
class CountingSortExample {
static int[] CountingSort(int[] arr) {
int max = arr.Max();
int[] count = new int[max + 1];
foreach (int x in arr)
count[x]++;
int index = 0;
for (int i = 0; i < count.Length; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
return arr;
}
static void Main() {
int[] nums = {4, 2, 5, 3, 3, 2, 1, 4};
nums = CountingSort(nums);
Console.WriteLine(string.Join(" ", nums));
}
}
