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

Call predictor: AI based call prediction

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