Softnami
Author: Hussain Mir Ali

I am interested in web and mobile technologies.

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

Announcements
Ads

Call predictor: AI based call prediction

Download

2020

Feb
Jan

2019

Dec
Nov
Jul
May
Mar
Jan

2018

Nov
Sep
Jul
Jun
Apr
Feb
Jan

2017

Dec
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Jan

2016

Dec
Oct
Sep
Aug
Jul

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.ts
UnsortedArray [ 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.