Quicksort in JavaScript

In my last article, I explained how to solve merge sort in JavaScript. Today, we will tackle quicksort - which is another algorithm that is very efficient when sorting arrays and datasets.

As for the merge sort algorithm we did in my previous post, this implementation will also be done in JavaScript.

Quicksort

As stated, quicksort is a sorting algorithm that will sort e.g an array of numbers, from the smallest to the biggest number. It will, as for merge sort, use a technique call divide and conquer - which basically means it will recursively split the array into smaller chunks as it processes the array. Another important rule of the quicksort, is the usage of a pivot.

Pivot (and partition)

What is a pivot? Well, in quicksort, a random index of the array is chosen (or always using the first or the last index is also common) and then the algorithm will partition all smaller numbers to the left of the pivot, and all the higher numbers on the right of the pivot. And after that, it will do the same for the left side of the pivot, and then for the right side. And it will continue to do so, until the subarrays are down to a single digit array - and once it is down to single digits, each of the partitioned subarrays are sorted and the algorithm is considered to be done.

Example

I will try to showcase an example of how it works before we jump into the code. If you need a wider explaination, Wikipedia has a very good page on this.

We start with an unsorted array of numbers:

[4,7,2,1,3]

We will set the pivot to the last index of the array (number 3). Then, we will move with two pointers, from first index and the first + 1 index until we are at the end of the array. Each number are compared to the pivot, and if the left pointer is greater than the pivot, and the right pointer is smaller than the pivot - they will swap places.

We start by comparing 4 with 3 and 7 with 3. Both are greater than 3, so nothing will happen.

[4,7,2,1,3]

Next iteration, we compare 4 and 3 and 2 and 3. Here, a swap is necessary since 4 > 3 and 2 < 3

[2,7,4,1,3]

Next, we compare 7 with 4 again, and 4 with 3. And as for the first step, nothing will happen.

[2,7,4,1,3]

Next, we compare 7 with 1 and 1 with 3 - here is a swap needed.

[2,1,4,7,3]

And now, our left pointer will be at position 2 (4) and it will compare to the pivot to check if a swap is needed. If the value is > than the pivot - we swap, otherwise we let it be. In this case, 4 > 3 so we will swap them.

[2,1,3,4,7]

Now, our pivot value that will be returned is index 2 (3). And we have two subarrays where the left is smaller than the pivot, and the right is bigger. Then the left part will be partitioned, and then the right part as well.

[2,1]
[1,2]

[4,7]

[1,2,3,4,7]

I hope it make sense. Otherwise, I suggest reading the Wikipedia link I linked to above, or head over to Youtube, which has a lot of great videos for explaining it with some great images etc.

Implementation

Now, let's implement this bad boy. We will create two functions, one for the recursion and one for the partitioning. We will break the recursion when the start and the end are the same (subarrays are down to one value). If start index are smaller than the end index, we will do the partitioning and get a new index for the pivot, and divide into subarrays - and continue into we hit a single digit subarray.

const sort = (arr, start, end) => {
  if (start >= end) {
    return;
  }

  const pivot = partition(arr, start, end);
  sort(arr, start, pivot - 1);
  sort(arr, pivot + 1, end);
};

After we have gotten our new pivot (basically the index of the pivot), we divide the array into left and right. So the left array will go from 0 to the pivot index - 1 (since we don't care about the pivot anymore since we know it is placed correct) and the right array is from pivot + 1 until the end of the array.

Partition

The biggest part (code wise) is the partitioning function. Here, we will loop through the array (or subarray) and swap the numbers accordingly. I will place some comments in the code for better understanding.

const partition = (arr, start, end) => {
  // Our pointers. They will move from the beginning of the array and beginning + 1 until the right pointer has entered the last index
  let leftPointer = start,
    rightPointer = start + 1;

  // Our pivot value
  let pivot = arr[end];
  // Loop until rightpointer is less than end index
  while (rightPointer < end) {
    // If the left index value is bigger than the pivot, and the right is less or equal to the pivot, we swap them.
    if (arr[leftPointer] > pivot && arr[rightPointer] <= pivot) {
      const left = arr[leftPointer];
      arr[leftPointer] = arr[rightPointer];
      arr[rightPointer] = left;
      leftPointer++;
      rightPointer++;

      // If the left is bigger than the pivot and the right pointer is also bigger, we only move the right pointer (so we can find the next smaller number, if any)
    } else if (arr[leftPointer] > pivot && arr[rightPointer] > pivot) {
      rightPointer++;

      // If left pointer is smaller than the pivot, we increase both pointers, since the number is already placed correct
    } else if (arr[leftPointer] <= pivot) {
      leftPointer++;
      rightPointer++;
    }
  }

  // When we are done, we check if the left pointer value is bigger than the pivot, if it is, we swap them and return the new index of the pivot
  if (arr[leftPointer] > pivot) {
    const left = arr[leftPointer];
    arr[leftPointer] = arr[end];
    arr[end] = left;
    return leftPointer;
  }

  // If the pivot was bigger than the last index for the left pointer, we will return the end index as our pivot
  return end;
};

Test

Now, we are ready to test it. We will start by just using a small array - and then we will do some simple performance test.

const array = [4, 7, 2, 1, 3];
sort(array, 0, array.length - 1);
console.log(array); // [ 1, 2, 3, 4, 7 ]

And now, let's sort hundred thousand numbers, and see how fast it is:

const arr = [];
for (let i = 0; i < 100000; i++) {
  const random = Math.floor(Math.random() * 1000);
  arr.push(random);
}

console.time("quicksort");
sort(arr, 0, arr.length - 1);
console.timeEnd("quicksort"); // 21.578ms

21,5 ms - that's alright I guess 😎

Outro

In this article, I shared a solution to the famous quicksort algorithm. If you are interested in more sorting algorithms, head over to our merge sort guide and have a look - it is almost as awesome as the quicksort 😃.

Do you have another solution, please contact us with your solution - we love to see it.

Thanks for reading!