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 #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 ]


Youtube Link: https://www.youtube.com/watch?v=sWm8a3Dh5jI&t=123s

💡 Practice Coding

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