QuickSort Algorithm

Quick Intro. I am in the process of studying algorithms and data structures myself. I write this to understand it a little better myself and with hope it might help somebody else. If something is to be improved, or not correct, please share.

The quicksort algorithm is the one I didn't get right away and had to spent a little more time on it to understand every moving piece. This probably happens with a lot of algorithms that involve recursion. So, here we go.

Overview

This is one of those algorithms that uses "Divide and conquer" technique. The point here is, that we solve this problem constantly dividing our input until it's solved fully.

This is also an "in place" algorithm, meaning that we move elements in the array, mutating the array, and we're not creating any new arrays to hold sorted values, and don't use any extra space for elements.

The whole idea revolves around the pivot element. This is the first step. Pick a pivot. It can be the first element, or the last one, or something in the middle. Doesn't really matter, but I'm going to be using the first one in the examples.

Now, that the pivot is picked. The next part is to place everything less than the pivot to the left of the pivot, and anything bigger to the right. This part also is called partition.

This means, that the element you picked first, your pivot, moves around, swaps places with elements bigger and smaller than itself, until it finds it's place in the array.

And then you call the function again for the part of the array that's to the right of the pivot, and to the left.
For this reason you should also keep track of the pivot index.

To recap, let's look at it step by step:

1. Declare a function, that accepts 3 arguments: array, starting index, ending index

2. Pick a pivot point

3. Keep track of the left and right indices. We will go to our pivot either from left to right, or from right to left. For this reason, we need to know, where we stand. Start by assigning left to starting index, right to ending index (I mean the start and end arguments passed into the function).

4. Now the partition process, which will continue while left index is less than the right one.

5. If a value you're looking at right index is less than pivot, it means it's in the wrong place. Swap them and update the pivot index.

6. Else if value at the left index is more than the value at the pivot index, swap them. Update the pivot index.

7. In this partition process keep track whether to move the right pointer further to the left, or the left pointer to the right. It's pretty simple, if the right index is more than the pivot, then decrement it. If the left one is less than the pivot, then increment that one. This works in my implementation, where the pivotIndex is the first element.

8. Do this until left index is smaller than the right index.

9. Now the recursive part. Call that function twice for the part of the array right of the right index, and for the part of the array left of the left index.

Code

function swap(arr, left, right) {
  let temp = arr[left];
  arr[left] = arr[right];
  arr[right] = temp;
}

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (arr.length <= 1 || high < 0 || low >= high) {
    return arr;
  }
  let pivotIndex = low;
  let left = low;
  let right = high;
  while (left < right) {
    if (arr[right] < arr[pivotIndex]) {
      swap(arr, pivotIndex, right);
      pivotIndex = right;
    } else if (arr[left] > arr[pivotIndex]) {
      swap(arr, pivotIndex, left);
      pivotIndex = left;
    }
    if (right > pivotIndex) {
      right--;
    } else if (left < pivotIndex) {
      left++;
    }
  }
  if (low < high) {
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

Other resources

Hungarian Folk Dance QuickSort

I've also made a video, if you prefer this format