Quicksort in JavaScript

Introduction

Sorting refers to arranging items of a list in a specific order (numerical or alphabetical). Sorting is generally used in tandem with searching.

Over the years, many sorting algorithms have been developed, and one of the fastest ones to date is Quicksort.

Quicksort uses the divide-and-conquer strategy to sort the given list of elements. This means that the algorithm breaks down the problem into subproblems until they become simple enough to solve directly.

Algorithmically this can be implemented either recursively or iteratively. However, the recursive approach is more natural for this problem.

Understanding the Logic Behind Quicksort

Let's take a look at how Quicksort works:

1. Select an element of the array. This element is generally called the pivot. Most often this element is either the first or the last element in the array.
2. Then, rearrange the elements of the array so that all the elements to the left of the pivot are smaller than the pivot and all the elements to the right are greater than the pivot. The step is called partitioning. If an element is equal to the pivot, it doesn't matter on which side it goes.
3. Repeat this process individually for the left and right side of the pivot, until the array is sorted.

Let's understand these steps further by walking through an example. Consider an array of unsorted elements [7, -2, 4, 1, 6, 5, 0, -4, 2]. We'll choose the last element to be the pivot. The step-by-step breakdown of the array would be as shown in the image below:

Elements that have been chosen as a pivot in one step of the algorithm have a colored outline. After partitioning, pivot elements are always in their correct positions in the array.

Arrays that have a bolded black outline represent the end of that specific recursive branch since we ended up with an array that contained only one element.

We can see the resulting sorting of this algorithm by simply going through the lowest element in each "column".

Implementation of Quicksort in JavaScript

As we could see, the backbone of this algorithm is the partitioning step. This step is the same regardless of whether we use the recursive or iterative approach.

With that in mind, let's first write the code to partition() an array:

function partition(arr, start, end){
    // Taking the last element as the pivot
    const pivotValue = arr[end];
    let pivotIndex = start; 
    for (let i = start; i < end; i++) {
        if (arr[i] < pivotValue) {
        // Swapping elements
        [arr[i], arr[pivotIndex]] = [arr[pivotIndex], arr[i]];
        // Moving to next element
        pivotIndex++;
        }
    }
    
    // Putting the pivot value in the middle
    [arr[pivotIndex], arr[end]] = [arr[end], arr[pivotIndex]] 
    return pivotIndex;
};

Here, we are taking the last element as the pivot. We are using a variable pivotIndex to keep track of the "middle" position where all the elements to the left are less, and all the elements to the right are more than the pivotValue.

As the last step, we swap the pivot, which is the last element in our case, with the pivotIndex. So, in the end, our pivot element would end up in the "middle." With all elements less than the pivot to the left side of it, and all elements greater than or equal to the pivot to the right of the pivot.

Recursive Implementation

Now that we have the partition() function, we have to recursively break this problem down and apply the partitioning logic in order to do the remaining steps:

function quickSortRecursive(arr, start, end) {
    // Base case or terminating case
    if (start >= end) {
        return;
    }
    
    // Returns pivotIndex
    let index = partition(arr, start, end);
    
    // Recursively apply the same logic to the left and right subarrays
    quickSort(arr, start, index - 1);
    quickSort(arr, index + 1, end);
}

In this function, we start by partitioning the array. After that, we partition both left and right subarrays. We repeat that process as long as the method receives an array that isn't empty or has more than one element.

This is because empty arrays, and arrays with only one element, are considered sorted.

Let's test this code out on our original example by calling:

array = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortRecursive(array, 0, array.length - 1)

console.log(array)

This would give us the output:

-4,-2,0,1,2,4,5,6,7

Iterative Implementation

As we mentioned previously, the recursive approach to Quicksort is much more intuitive. However, implementing Quicksort iteratively is a relatively common interview question for Software Engineers.

As with most recursive-to-iterative conversions, the first thing that should come to mind is using a stack to simulate recursive calls. This is done so we can reuse some of the recursive logic that we're familiar with, and use it in an iterative setting.

We need to somehow keep track of what unsorted subarrays we have left. One way to do this is to simply keep "pairs" of elements in a stack, representing the start and end of a given unsorted subarray.

JavaScript doesn't have an explicit stack data structure, but arrays support the push() and pop() functions. They don't support the peek() function however, so we will have to manually check the top of the stack using stack[stack.length - 1].

We'll be using the same partition function as we did for the recursive approach. Let's see how to write the Quicksort part:

function quickSortIterative(arr) {
    // Creating an array that we'll use as a stack, using the push() and pop() functions
    stack = [];
    
    // Adding the entire initial array as an "unsorted subarray"
    stack.push(0);
    stack.push(arr.length - 1);
    
    // There isn't an explicit peek() function
    // The loop repeats as long as we have unsorted subarrays
    while(stack[stack.length - 1] >= 0){
        
        // Extracting the top unsorted subarray
        end = stack.pop();
        start = stack.pop();
        
        pivotIndex = partition(arr, start, end);
        
        // If there are unsorted elements to the "left" of the pivot,
        // we add that subarray to the stack so we can sort it later
        if (pivotIndex - 1 > start){
            stack.push(start);
            stack.push(pivotIndex - 1);
        }
        
        // If there are unsorted elements to the "right" of the pivot,
        // we add that subarray to the stack so we can sort it later
        if (pivotIndex + 1 < end){
            stack.push(pivotIndex + 1);
            stack.push(end);
        }
    }
}

Let's test this code on our example as well, by calling:

ourArray = [7, -2, 4, 1, 6, 5, 0, -4, 2]
quickSortIterative(ourArray)

console.log(ourArray)

We get the expected output of:

-4,-2,0,1,2,4,5,6,7

Visualization of Quick Sort

When it comes to sorting algorithms, it's always good to visualize them. It just helps us "see" them in action Here is an example of how the Quicksort algorithm works:

Source: Wikipedia

In this case, the pivot is also taken as the last element. After the given array is partitioned, the left side is recursively gone through until it's completely sorted. Then the algorithm comes to the right side and does the sorting.

The Efficiency of Quick Sort

Now that we know how to implement the Quicksort algorithm let us discuss the time and space complexity. The worst-case time complexity of Quick Sort is O(n²). The average case time complexity is O(nlogn). The worst-case is usually avoided by using a randomized version of Quicksort.

The weak spot of the Quicksort algorithm is the choice of the pivot. Choosing a bad pivot (one that is greater than/less than most elements) every time, would give us the worst-case time complexity. While repeatedly choosing a pivot that has a roughly equal number of elements that are less than/greater than the pivot would give us a time complexity of O(nlogn).

Quicksort is one of those algorithms where the average-case runtime is actually important. Empirically, it was noticed that Quicksort tends to have a O(nlogn) runtime regardless of the pivot-choosing strategy.

Also, when it comes to space complexity, Quicksort doesn't take any extra space (excluding the space reserved for recursive calls). These kinds of algorithms are technically called as in-place algorithms. We don't need extra space because we are performing the operation on the same array.

Conclusion

In this article, we've gone over the theory behind Quicksort and then implemented it recursively and iteratively using JavaScript.