Introduction to the Quicksort Algorithm
If you’re interviewing for a developer position, one of the more intimidating questions that you can be asked is to explain how the Quicksort algorithm works. It’s a popular interview question by companies such as Facebook and Google, so I thought it would be a good one to cover.
Guide Tasks
  • Read Tutorial
  • Watch Guide Video
Video locked
This video is viewable to users with a Bottega Bootcamp license
APPLY NOWLEARN MORE

Quicksort is one of the most popular sorting algorithms used by programmers due to it’s performance and space efficiency.

Here are some facts to know about Quicksort:

  • In average cases it has a performance of O(n lg n), if you are unfamiliar with the Big-O notation, just know that O(n lg n) is one of the best performing algorithm speeds for any sorting algorithm
  • It’s worst case performance is O(n^2), this is very slow, but rarely occurs
  • It is not a stable sort algorithm, which means that the original order of the elements is not preserved. As an example this would mean that if you placed multiple 5’s in an array, there’s no way to guarantee that the 5’s will all be in the same order that you placed them in the array after it’s been sorted, as shown here.
  • It is in the category of divide and conquer algorithms. Divide and conquer is a category of algorithm where the main task is broken into a set of smaller tasks and processed before putting all of the components back together at the end. I like divide and conquer algorithms because that’s also how I like to learn, I like to break down a difficult topic into its smallest, most easy to understand concept and then work my way up to advanced techniques.
  • One of the most important items to remember about Quicksort is that it uses a pivot element to partition the data set up into smaller pieces. And it does it over and over again until the full set of values are sorted.

The algorithm takes the following steps:

  1. Picks a pivot element, usually you’ll select a random element as the pivot
  2. Then it partitions the array into three sections: all of the elements less than the pivot which are located left of the pivot, the pivot itself, and all of the elements greater than the pivot located to the right of the pivot
  3. Lastly it runs steps 1 and 2 on the left and right partitions recursively until the full partition is sorted

I’ve seen university lectures that discuss the Quicksort algorithm for hours, so hitting all of the points in 5 minutes isn’t practical, however all of the items that I’ve discussed should help in a programming interview and in the resource section I’ve included links, including: animations of how Quicksort works, a code implementation that I wrote in Ruby, and some long form videos.

Resources