Counting Sort is a non-comparison-based sorting algorithm that sorts integers by
counting the occurrences of each distinct value in a range and using this
information to place elements in their correct positions. It works in 𝑂(𝑛+𝑘)
time, where 𝑛 is the number of elements and 𝑘 is the range of the input values.
Counting Sort is efficient for small ranges of integers but unsuitable for
sorting non-integer or large-range data due to its space complexity of 𝑂(𝑘). It
is a stable sorting algorithm when implemented correctly.
/**
* @file Counting Sort
* @author Dustin Boston
* @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
* Introduction to Algorithms. (2nd ed). The MIT Press.
*/
/**
* Sorts an array of non-negative integers using the counting sort algorithm.
* This algorithm is efficient for sorting numbers within a small range.
*
* @param unsortedArray The array of non-negative integers to be sorted.
* @param maxValueInArray The maximum value in the array. Used to find the range
* of vals.
* @returns A new array containing the sorted elements.
*/
export function countingSort (
unsortedArray : number [],
sortedArray : number [],
maxValueInArray : number ,
) : void {
const counts : number [] = Array . from ({ length : maxValueInArray + 1 }, () => 0 );
// Update the `count` array with positions of elements in the sorted array
for ( const element of unsortedArray ) {
counts [ element ] ++ ;
}
for ( let i = 1 ; i <= maxValueInArray ; i ++ ) {
counts [ i ] += counts [ i - 1 ];
}
for ( let index = unsortedArray . length - 1 ; index >= 0 ; index -- ) {
sortedArray [ counts [ unsortedArray [ index ]] - 1 ] = unsortedArray [ index ];
counts [ unsortedArray [ index ]] -- ;
}
}
import { describe , expect , test } from "bun:test" ;
import { countingSort } from "./code.ts" ;
describe ( "Counting Sort" , () => {
test ( "Sort" , () => {
const unsortedArray = [ 2 , 5 , 3 , 0 , 2 , 3 , 0 , 3 ];
const maxValueInArray = Math . max (... unsortedArray );
const sortedArray : number [] = Array . from (
{ length : unsortedArray.length },
() => 0 ,
);
countingSort ( unsortedArray , sortedArray , maxValueInArray );
const expectedArray = [ 0 , 0 , 2 , 2 , 3 , 3 , 3 , 5 ]. toString ();
const actualArray = sortedArray . toString ();
expect ( actualArray ). toBe ( expectedArray );
});
});