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 #1: Quick Sort using TypeScript


In this post I have implemented the Quick sort algorithm. This algorithm has a worst case time complexity of O(n^2) and an average case time complexity of O(nlogn). It has a worst case space complexity of O(logn) which comes from the call stack for recursive calls.

/**
 * This class contains logic for Quick Sort algorithm implementation.
 *
 * @class QuickSort
 * @constructor
 */
export class QuickSort {

private arr: number[];

constructor() {}
/**
     * Starts the soring process.
     *
     * @method sort
     * @param {Array} arry The array to be sorted.
     */
public sort(arry: number[]): void {
if (arry !== undefined) {
this.arr = arry;
this.quicksort(0, this.arr.length - 1);
}
}

/**
   * Swaps array according to given indices.
   *
   * @method swap
   * @param {Number} i Index of array to swap.
   * @param {Number} j Index of array to swap.
   */
public swap(i: number, j: number): void {
let temp: number = this.arr[i];
this.arr[i] = this.arr[j];
this.arr[j] = temp;
}

/**
   * Sorts array in O(nlogn) time average case and O(n^2) worst case. With space complexity of O(logn).
   *
   * @method quicksort
   * @param {Number} low The lower-end index of array.
   * @param {Number} high The higher-end index of array.
   */
public quicksort(low: number, high: number): void {
let i: number = low;
let j: number = high;
let pivot: number = this.arr[Math.floor((low + high) / 2)];

while (i <= j) {

while (this.arr[i] < pivot) {
i++;
}

while (this.arr[j] > pivot) {
j--;
}

if (i <= j) {
this.swap(i, j);
i++;
j--;
}
}

if (low < j) {
this.quicksort(low, j);
}
if (i < high) {
this.quicksort(i, high);
}
}

}

Usage:
import {QuickSort} from './Quicksort'

let arry:number[] = [];

for(let i = 0; i<10; i++){
arry[i] =Math.floor(Math.random() * 16) + 1;
}

console.log('Unsorted',arry);

let sorter:QuickSort = new QuickSort();
sorter.sort(arry);

console.log('Sorted',arry);

Output:
hxce@ubuntu:~/Desktop/Quicksort$ ts-node main.ts
Unsorted [ 9, 5, 8, 7, 2, 2, 14, 15, 5, 7 ]
Sorted [ 2, 2, 5, 5, 7, 7, 8, 9, 14, 15 ]


💡 Practice Coding

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