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