Counting Sort — VisualAlgorithms Docs

How it works

Counts occurrences of each value and uses arithmetic to place elements. Very fast when the range k is not much larger than n.

Implementation

      
 function countingSort(arr, stats) {
  const n = arr.length;
  if (n < 2) return;
  let max = arr[0];
  for (let i = 1; i < n; i++) {
    if (arr[i] > max) max = arr[i];
  }
  const count = new Array(max + 1).fill(0);
  for (let i = 0; i < n; i++) {
    count[arr[i]]++;
  }
  let idx = 0;
  for (let v = 0; v <= max; v++) {
    while (count[v] > 0) {
      arr[idx] = v;
      idx++;
      count[v]--;
    }
  }
} def sort(arr, n, stats):
    if (n < 2):
        return
    max = arr[0]
    for i in range(1, n):
        if (arr[i] > max):
            max = arr[i]
    count = [0] * (max + 1)
    for i in range(n):
        count[arr[i]] += 1
    idx = 0
    for v in range((max + 1)):
        while (count[v] > 0):
            arr[idx] = v
            idx += 1
            count[v] -= 1 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    std::vector<int> count((max + 1), 0);
    for(int i=0; i<n; i++) {
        count[arr[i]]++;
    }
    int idx = 0;
    for(int v=0; v<(max + 1); v++) {
        while((count[v] > 0)) {
            arr[idx] = v;
            idx++;
            count[v]--;
        }
    }
} public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int[] count = new int[(max + 1)];
    for(int i=0; i<n; i++) {
        count[arr[i]]++;
    }
    int idx = 0;
    for(int v=0; v<(max + 1); v++) {
        while((count[v] > 0)) {
            arr[idx] = v;
            idx++;
            count[v]--;
        }
    }
} #include <stdio.h>
#include <string.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if((arr[i] > max)) {
            max = arr[i];
        }
    }
    int count[(max + 1)]; memset(count, 0, sizeof(count));
    for(int i=0; i<n; i++) {
        count[arr[i]]++;
    }
    int idx = 0;
    for(int v=0; v<(max + 1); v++) {
        while((count[v] > 0)) {
            arr[idx] = v;
            idx++;
            count[v]--;
        }
    }
} 