Buildtide
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 #3: Insertion Sort using TypeScript

In this blog post I have implemented insertion sort algorithm. The best use case is when an array is partially sorted and this algorithm is used to fully sort it.

For partially sorted array the worst case time complexity is O(n) otherwise the complexity is O(n^2).
The space complexity is O(1).

Implementation:
/**
*This class contians information to sort a number array using insertion sort.
*
*@class InsertionSort
*@constructor
**/
export class InsertionSort{

constructor(){

}

/**
*This method contains logic to sort a partially sorted array in O(n) time.
*@method sort
*@param {Array} arr The array to be sorted.
*@return {Array} arr THe sorted array.
**/
public sort(arr:number[]):number[]{

if(arr!==undefined){
for(let i:number = 0; i< arr.length; i++){

let j = i-1;
let key = arr[i];

while(j>-1 && arr[j]>key){
arr[j+1] = arr[j];
j--;
}

arr[j+1] = key;

}
return arr;
}

}

}

Usage:
import {InsertionSort} from './Insertionsort';

let sorter:InsertionSort = new InsertionSort();
let dummyarray:number[] = [];

for(let i:number=0; i<15; i++){

dummyarray[i] = Math.floor(Math.random()*290+1);

}

console.log("Unsorted Array", dummyarray);

dummyarray = sorter.sort(dummyarray);

console.log("Sorted Array", dummyarray);

Output:
hxce@ubuntu:~/Desktop/Insertionsort\$ ts-node main.ts
Unsorted Array [ 57, 209, 160, 238, 216, 179, 63, 223, 80, 197, 84, 222, 207, 158, 243 ]
Sorted Array [ 57, 63, 80, 84, 158, 160, 179, 197, 207, 209, 216, 222, 223, 238, 243 ]