Algorithms #3: Insertion Sort using TypeScript

Friday, March 31st, 2017

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.