Counting Sort (Stable) Code
Time Complexity
O(n + k)
where k: range.
if k <<<< n, it's a very stable algorithm.
Space Complexity
O(K)
function countingSortStable(arr) {
let max = Math.max(...arr);
let count = new Array(max + 1).fill(0);
for(let x of arr){
count[x]++;
}
let prefix = new Array(max + 1).fill(0);
prefix[0] = count[0];
for(let i = 1; i < count.length; i++){
prefix[i] = count[i] + prefix[i - 1];
}
let sortedArr = new Array(arr.length);
for(let i = arr.length - 1; i >= 0; i--) {
let curr = arr[i];
let x = prefix[curr];
sortedArr[x-1] = curr;
prefix[curr]--
}
return sortedArr;
}
let nums = [4, 2, 5, 3, 3, 2, 1, 4];
console.log(countingSortStable(nums));
def counting_sort_stable(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
for x in arr:
count[x] += 1
prefix = [0] * (max_val + 1)
prefix[0] = count[0]
for i in range(1, len(count)):
prefix[i] = prefix[i - 1] + count[i]
sorted_arr = [0] * len(arr)
for i in range(len(arr) - 1, -1, -1):
curr = arr[i]
sorted_arr[prefix[curr] - 1] = curr
prefix[curr] -= 1
return sorted_arr
nums = [4, 2, 5, 3, 3, 2, 1, 4]
print(counting_sort_stable(nums))
import java.util.*;
public class CountingSortStable {
public static int[] countingSortStable(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int[] count = new int[max + 1];
for (int x : arr) {
count[x]++;
}
int[] prefix = new int[max + 1];
prefix[0] = count[0];
for (int i = 1; i <= max; i++) {
prefix[i] = prefix[i - 1] + count[i];
}
int[] sortedArr = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
int curr = arr[i];
sortedArr[prefix[curr] - 1] = curr;
prefix[curr]--;
}
return sortedArr;
}
public static void main(String[] args) {
int[] nums = {4, 2, 5, 3, 3, 2, 1, 4};
int[] res = countingSortStable(nums);
System.out.println(Arrays.toString(res));
}
}
#include <bits/stdc++.h>
using namespace std;
vector countingSortStable(vector& arr) {
int maxVal = *max_element(arr.begin(), arr.end());
vector count(maxVal + 1, 0);
for (int x : arr) {
count[x]++;
}
vector prefix(maxVal + 1, 0);
prefix[0] = count[0];
for (int i = 1; i <= maxVal; i++) {
prefix[i] = prefix[i - 1] + count[i];
}
vector sortedArr(arr.size());
for (int i = arr.size() - 1; i >= 0; i--) {
int curr = arr[i];
int pos = prefix[curr];
sortedArr[pos - 1] = curr;
prefix[curr]--;
}
return sortedArr;
}
int main() {
vector nums = {4, 2, 5, 3, 3, 2, 1, 4};
vector res = countingSortStable(nums);
for (int x : res) cout << x << " ";
return 0;
}
#include <stdio.h>
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
void countingSortStable(int arr[], int n) {
int maxVal = findMax(arr, n);
int count[maxVal + 1];
int prefix[maxVal + 1];
int output[n];
for (int i = 0; i <= maxVal; i++)
count[i] = 0;
for (int i = 0; i < n; i++)
count[arr[i]]++;
prefix[0] = count[0];
for (int i = 1; i <= maxVal; i++)
prefix[i] = prefix[i - 1] + count[i];
for (int i = n - 1; i >= 0; i--) {
int curr = arr[i];
output[prefix[curr] - 1] = curr;
prefix[curr]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
int main() {
int nums[] = {4, 2, 5, 3, 3, 2, 1, 4};
int n = sizeof(nums) / sizeof(nums[0]);
countingSortStable(nums, n);
for (int i = 0; i < n; i++)
printf("%d ", nums[i]);
return 0;
}
using System;
using System.Linq;
class Program {
static int[] CountingSortStable(int[] arr) {
int max = arr.Max();
int[] count = new int[max + 1];
foreach (int x in arr)
count[x]++;
int[] prefix = new int[max + 1];
prefix[0] = count[0];
for (int i = 1; i <= max; i++)
prefix[i] = prefix[i - 1] + count[i];
int[] sortedArr = new int[arr.Length];
for (int i = arr.Length - 1; i >= 0; i--) {
int curr = arr[i];
sortedArr[prefix[curr] - 1] = curr;
prefix[curr]--;
}
return sortedArr;
}
static void Main() {
int[] nums = {4, 2, 5, 3, 3, 2, 1, 4};
int[] result = CountingSortStable(nums);
Console.WriteLine(string.Join(" ", result));
}
}
