Quick sort algorithm in Javascript

Posted on | by Prashant Yadav

Posted in ,

Learn what is Quicksort and how to implement Quick sort (with all different partition variations) algorithm in javascript.

List of sorting algorithms

Quicksort also know as partition-exchange sort, is one of the most efficient sorting algorithms.

It was developed by British computer scientist Tony Hoare in 1959 and published in 1961.

It does comparison based sorting but is not so stable, which means the relative order of the elements is not preserved.

Like merge sort, quick sort also uses the divide and conquer paradigm to sort the elements. It picks an element as a pivot and partitions the elements around this pivot. There are many different versions of quicksort that pick pivot in different ways.

It also has the advantage of sorting in place and it works well even in virtual memory environments.

How quick sort works?

Conceptually this is how it works.

As it is a divide and conquer algorithm, we will perform the each action in this way.

  • Divide:- Pick a pivot q and partition the array arr[p...r]into two possible sub arrays arr[p...q-1], arr[q+1...r] such that all the elements of the left sub arrayarr[p...q-1] is less than the pivot and all the elements of the right sub arrayarr[q+1...r] is greater than the pivot. After this we are sure that the pivot q is sorted, but the left and right sub arrays may or may not be sorted.
  • Conquer:- Sort the two sub arrays arr[p...q-1], arr[q+1...r] by calling itself recursively.
  • Combine:- As all the sub array is sorted, there is no need to combine them.

Quick Sort Javascript

Psuedo Code

quickSort(arr, p, r){
if p < r
   q = partition(arr, p, r)
   quickSort(arr, p, q - 1)
   quickSort(arr, q + 1, r)
}

partition(arr, p, r){
  //Last element as pivot
  q = arr[r]
  i = p - 1
  for j = p to r - 1
     if arr[j] <= q
        i = i + 1
        swap arr[i] with arr[j]
  swap arr[i + 1] with arr[r]
  return i + 1
}

The most challenging part of quicksort is partitioning the array properly into two parts, if done properly it is two to three times faster than merge sort & heap sort.

The following image illustrates the working cycle of a partition in a single call.

Pivot partition cycle quick sort

Quick sort algorithm in Javascript.

Based on the above pseudo-code we will implement all the different variations of the quicksort in javascript.

The first two partition method in which we use first and last element as a pivot is based on Lomuto partition scheme.

In each implementation we will use a helper function to swap the two elements in the array.

const swap = (arr, left, right) =>  {
  const temp = arr[left]
  arr[left] = arr[right]
  arr[right] = temp;
}

First element as a pivot

const partitionLow = (arr, low, high) => {
  //Pick the first element as pivot
  let pivot = arr[low];
  let i = low;
  
  //Partition the array into two parts using the pivot
  for(let j = low; j <= high; j++){
    if(arr[j] <= pivot){ 
      swap(arr, i, j);
      i++;
    }
  }
  
  swap(arr, i - 1, low);
  
  //Return the pivot index
  return i - 1;
}

const quicksort = (arr, low, high) => {
    // base condition
    if (low >= high) {
      return;
    }

    // rearrange the elements across pivot
    const pivot = partitionLow(arr, low, high);

    // recur on sub-array containing elements less than pivot
    quicksort(arr, low, pivot - 1);

    // recur on sub-array containing elements more than pivot
    quicksort(arr, pivot + 1, high);
}

Input:
let arr = [10, 7, 8, 9, 1, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr);

Output:
[1, 5, 7, 8, 9, 10]

Last element as pivot

const partitionHigh = (arr, low, high) => {
  //Pick the first element as pivot
  let pivot = arr[high];
  let i = low;
  
  //Partition the array into two parts using the pivot
  for(let j = low; j < high; j++){
    if(arr[j] <= pivot){      
      swap(arr, i, j);
      i++;
    }
  }
  
  swap(arr, i, high);
  
  //Return the pivot index
  return i;
}

const quicksort = (arr, low, high) => {
    // base condition
    if (low >= high) {
      return;
    }

    // rearrange the elements across pivot
    const pivot = partitionHigh(arr, low, high);

    // recur on sub-array containing elements less than pivot
    quicksort(arr, low, pivot - 1);

    // recur on sub-array containing elements more than pivot
    quicksort(arr, pivot + 1, high);
}

Input:
let arr = [10, 7, 8, 9, 1, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr);

Output:
[1, 5, 7, 8, 9, 10]

Middle element as pivot

Using middle element as pivot is little tricky as it uses Hoare partition scheme.

This scheme works as follows.

  • Use two indices that start at the ends of the array being partitioned.
  • Then move towards each other until they discover an inversion, i.e a pair of elements, one greater than or equal to the pivot, one less than or equal, that are in the wrong order relative to each other.
  • The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index.
const partitionMiddle = (arr, low, high) => {
  //Get the mid index
  const mid = Math.floor((low + high) / 2);
  //Swap the mid element with first element
  swap(arr, mid, low);
  
  //Now use the first element as pivot
  let pivot = arr[low];
  let lo = low + 1;
  let hi = high;
  
  //Partition the array based on the pivot
  while(lo <= hi){
    //Move towards each other
    while(arr[hi] > pivot){
      hi = hi - 1
    }
    
    while(lo <= hi && arr[lo] <= pivot){
      lo = lo + 1;
    }
    
    //When inversion found swap the elements
    if(lo <= hi){
      swap(arr, lo, hi);
      lo = lo + 1;
      hi = hi - 1;
    }
  }
  
  swap(arr, low, hi);
  
  //Return the pivot index
  return hi;
}

const quicksort = (arr, low, high) => {
    // base condition
    if (low >= high) {
      return;
    }

    // rearrange the elements across pivot
    const pivot = partitionMiddle(arr, low, high);

    // recur on sub-array containing elements less than pivot
    quicksort(arr, low, pivot - 1);

    // recur on sub-array containing elements more than pivot
    quicksort(arr, pivot + 1, high);
}

Input:
let arr = [10, 7, 8, 9, 1, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr);

Output:
[1, 5, 7, 8, 9, 10]

Random element as a pivot.

It is highly anticipated that the randomized version of quick sort as the sorting algorithm of choice for large enough inputs.

The idea is to choose a random index from the given index of the array and then perform the quick sort using either one of the above partitions. Generally the first or the last element as a pivot is used.

const partitionRandom = (arr, low, high) => {
  //Get random number between the given indexes.
  const random = Math.floor(Math.random() * (high - low + 1) + low);

  //Swap with the first element
  swap(arr, random, low);

  //Use first element as a pivot
  return partitionLow(arr, low, high);
}

const partitionLow = (arr, low, high) => {
  //Pick the first element as pivot
  let pivot = arr[low];
  let i = low;
  
  //Partition the array into two parts using the pivot
  for(let j = low; j <= high; j++){
    if(arr[j] <= pivot){ 
      swap(arr, i, j);
      i++;
    }
  }
  
  swap(arr, i - 1, low);
  
  //Return the pivot index
  return i - 1;
}

const quicksort = (arr, low, high) => {
    // base condition
    if (low >= high) {
      return;
    }

    // rearrange the elements across pivot
    const pivot = partitionRandom(arr, low, high);

    // recur on sub-array containing elements less than pivot
    quicksort(arr, low, pivot - 1);

    // recur on sub-array containing elements more than pivot
    quicksort(arr, pivot + 1, high);
}

Input:
let arr = [10, 7, 8, 9, 1, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr);

Output:
[1, 5, 7, 8, 9, 10]

Analysis of quick sort algorithm implemented in javascript.

If we break down the recurrence relation of quick sort and try to solve it with master method, then in mathematical term it can be written as.

T(n) = T(k) + T(n-k-1) + O(n)

T(k) is the first recursive call, T(n-k-1) is the second recursive call and O(n) is the time taken for partitioning.

The time taken by quick sort depends upon the input array and partition strategy. The following are three cases.

Worst case

The worst case occurs when the partition process always picks the first or last element as pivot. If we consider the above partition strategy where the last element is always picked as a pivot, the worst case would occur when the array is already sorted in increasing or decreasing order.

T(n) = T(0) + T(n-1) + O(n)

which is equivalent to  

T(n) = T(n-1) + O(n)

Now after solving this we get

O(n^2)

Best case

The best case occurs when the partition process always picks the middle element as pivot.

T(n) = 2T(n/2) + O(n)

after solving this with master theorem we get

O(nlogn)

Average case

For average case analysis, we need to consider all possible permutation of the array and calculate the time taken by every permutation which doesn’t look easy.

We can get an idea of average case by considering the case when partition puts O(n/9) elements in one sub array and O(9n/10) elements in other.

T(n) = T(n/9) + T(9n/10) + O(n)

after solving this we get

O(nlogn)
Best Average Worst
Θ(NlogN) Θ(NlogN) Θ(N^2)

Although the worst case of quicksort is O(n ^ 2) which may seem worse than merge sort and heap sort. Quicksort is faster in practice because its inner loop can be efficiently implemented on most architectures, and in most real-world data.

Optimizing the quick sort using tail recursion.

To make sure at most O(logn) space is used, recur first into the smaller side of the partition, the use a tail call to recur into the other. With this we successfully sort the array in a way that it minimizes the recursive depth.

let partitionHigh = (arr, low, high) => {
  //Pick the first element as pivot
  let pivot = arr[high];
  let i = low;
  
  //Partition the array into two parts using the pivot
  for(let j = low; j < high; j++){
    if(arr[j] <= pivot){      
      swap(arr, i, j);
      i++;
    }
  }
  
  swap(arr, i, high);
  
  //Return the pivot index
  return i;
}

const tailRecursiveQuickSort = (arr, low, high) => {
  while(low < high){
    const PI = partitionHigh(arr, low, high);
    
    // recur on smaller sub-array
    if (PI - low < high - PI) {
	tailRecursiveQuickSort(arr, low, PI - 1);
	low = PI + 1;
    }
    else {
	tailRecursiveQuickSort(arr, PI + 1, high);
	high = PI - 1;
    }
  }
}

Input:
let arr = [10, 7, 8, 9, 1, 5];
tailRecursiveQuickSort(arr, 0, arr.length - 1);
console.log(arr);

Output:
[1, 5, 7, 8, 9, 10]

Introducing frontend system design course 🔥 where you will learn to design frontend of 30+ applications.