QuickSort implementation in TypeScript using recursion

This post will discuss how to implement the QuickSort algorithm in typescript/javascript. Quicksort is the fastest algorithm. Quicksort works on the divide and conquer strategy. All languages in the world provide sorting functionality which implements QuickSort with some modifications.

What is divide and conquer

As per the Wikipedia

A divide-and-conquer algorithm breaks down a problem into two or more sub-problems of the same or similar type in a recursive manner. Wikipedia

Choosing Pivot Point

Choosing a pivot point is also very important in QuickSort. You can select first, last or middle as a pivot element.

Quicksort algorithm follows the following steps.

Step 1 Choose the pivot element.

Step 2 Divide the array into two pieces, one smaller than the pivot and the other larger.

Step 3 recursively sort the left half.

Step 4 recursively sort the right half.

The complexity of QuickSort is

• Best Case O(nlogn).
• Worst cases O(n^2).

Implementation

export function QuickSort(
  arr: Array<number>,
  start: number = 0,
  end: number = arr.length
): Array<number> {
  if (start < end) {
    let p = partition(arr, start, end);
    QuickSort(arr, start, p - 1);
    QuickSort(arr, p + 1, end);
  }
  return arr;
}

function partition(
  arr: Array<number>,
  start: number = 0,
  end: number = arr.length
) {
  let pivot: number = arr[start];
  let swapIndex: number = start;
  for (let i = start + 1; i < end; i++) {
    if (arr[i] < pivot) {
      swapIndex++;
      swap(arr, i, swapIndex);
    }
  }
  swap(arr, start, swapIndex);
  return swapIndex;
}

function swap(arr: Array<number>, i: number, j: number) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}