Data Structures and Algorithms: Quick Sort

The quick sort is a divide and conquer algorithm. This algorithm can be used to quickly order any given array.

How it works

Given an array as input, we start by selecting an element of the array to act as the pivot.

We then walk through the array, comparing each element to the pivot. Elements that are less than the pivot are placed to the left whilst elements that are greater than than the pivot are placed to the right. This will result in a weakly sorted array after the first run through.

In order to further sort the array, we now select a pivot for the elements to the left and a separate pivot for the elements on the right.

We then proceed to repeat the process until we get to an empty array or an array with a single element.

The single element arrays are then concatenated into a new sorted array.

Below I will demonstrate how this can be applied in JavaScript using recursion.

1. Select pivot

There are many ways in which a pivot can be selected. Some prefer to use the first element in the array and others prefer to select an element from somewhere in the middle. As a personal preference I like to select the last element of the array.

  let pivot = array[array.length - 1];

2. Establish base case

Following the lead from the previous article, we will proceed to establish a base case for the recursive algorithm. When the array has only one element it will no longer need to call the function, as this single element array is already sorted.

 if (array.length <= 1) {
    return array;
  }

3. Split

Now we will split our array into two separate subarrays. All elements of the array found to have values smaller than the pivot will be put into one subarray, and all elements found to have values greater than the pivot will be put into another subarray.

  let low = [];
  let high = [];

  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      low.push(array[i]);
    } else {
      high.push(array[i]);
    }
  }

4. Establish recursive case

Lastly, we need to provide the recursive case for the function. Here the quick sort function will be called on the two separate subarrays until they reach the base case, at which point they will be concatenated with the pivot to return a sorted array.

return [...QuickSort(low), pivot, ...QuickSort(high)];

Here we use the spread operator(...) to merge the elements of the subarrays into the sorted array.

Here is the complete code for the algorithm.

function QuickSort(array) {
  if (array.length <= 1) {
    return array;
  }
  let pivot = array[array.length - 1];
  let low = [];
  let high = [];

  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] < pivot) {
      low.push(array[i]);
    } else {
      high.push(array[i]);
    }
  }
  return [...QuickSort(low), pivot, ...QuickSort(high)];
}

Conclusion

This concludes the basics of the quick sort algorithm. It is an incredibly popular algorithm, mainly due to its relative speed and its simplicity, with the added advantage of not needing extra memory. It is a great choice when one wants to search a dataset for information.