Author: Hussain Mir Ali

I am interested in web and mobile technologies.

If you have any questions or feedback then message me at devtips@Buildtide.com.

# Algorithms #4: Counting Sort

The Counting sort algorithm is useful for sorting number arrays of length n where the numbers are in a certain range from 0 to k. This algorithm has been implemented in TypeScript.

Time Complexity: O(n+k)

Space Complexity: O(n+k)

Implementation:
`/** *This class has logic to implement counting sort algorithm. *@constructor *@class Countingsort */export class Countingsort {  constructor() {}  /**   *This method has logic to sort an array with numbers in a certain range in O(n) time.   *@method sort   *@param {Array} arry The array to be sorted.   *@return {Array} sortedArry The sorted array.   */  public sort(arry: number[]): number[] {    if (arry !== undefined) {      let sortedIndex: number = 0;      let sortedArry: number[] = [];      let numofCounts: number[] = [];      for (let i of arry) {        if (numofCounts[i] === undefined) {          numofCounts[i] = 0;        }        numofCounts[i] += 1;      }      for (let i = 0; i < numofCounts.length; i++) {        let count = numofCounts[i];        for (let j = 0; j < count; j++) {          sortedArry[sortedIndex] = i;          sortedIndex++;        }      }      return sortedArry;    }    return [];  }}`

Usage:
`import {Countingsort} from './Countingsort';let unsortedArray: number[] = [];let sortedArray: number[] = [];for (let i = 0; i < 10; i++) {  unsortedArray[i] = Math.floor(Math.random() * 5 + 0);}for (let i = 0; i < 10; i++) {  let randomindex = Math.floor(Math.random() * 9 + 0);  let temp = unsortedArray[i];  unsortedArray[i] = unsortedArray[randomindex];  unsortedArray[randomindex] = temp;}console.log('UnsortedArray', unsortedArray);let sorter: Countingsort = new Countingsort();sortedArray = sorter.sort(unsortedArray);console.log('Sorted Array', sortedArray);`

Output:
`hxce@ubuntu:~/Desktop/Countingsort\$ ts-node main.tsUnsortedArray [ 4, 1, 3, 2, 3, 1, 3, 4, 0, 4 ]Sorted Array [ 0, 1, 1, 2, 3, 3, 3, 4, 4, 4 ]`

### ðŸ’¡ Practice Coding

Practice coding questions from top companies like Google, Amazon, Apple, and others. Signup today at Softnami's daily coding.