Divide and Conquer Algorithms — QuickSort
In my last article, I chose to dive in to the “Divide and Conquer” algorithmic paradigm, and what I found was quite interesting!
For one, I realized the importance of being able to sort arrays in programming. It is a common task you will find yourself attempting to complete. As I explained in my last article, there are built in functions for sorting in many programming languages, such as sort() in JavaScript, but as programmers we don’t always want to choose the easy way, we want to know how it’s done!
Another thing I realized when learning about Divide and Conquer algorithms is how incredibly genius the idea of it is! Let’s go over the steps of a Divide and Conquer algorithm once again.
Divide and Conquer
Divide and Conquer is a programming paradigm that Merge Sort and Quicksort algorithms use. It is an algorithm based on recursion, and it is broken down into 3 main steps:
- Divide the problem into subproblems that are simply smaller instances of the original problem.
- Conquer the subproblems by solving them recursively. If the problem is small enough, then that is the base problem.
- Combine the solutions to the subproblems to the solution for the original problem
Here’s what it looks like:
Pretty cool stuff! I applaud the mathematician that came up with this algorithm!
Now let’s take a deeper look at QuickSort and what it’s all about.
QuickSort
QuickSort is similar to Merge Sort, but there are a few differences. Merge Sort is broken down into 3 steps:
- Divide
- Conquer
- Combine
The majority of the work in a Merge Sort is done in the Combine step. In a QuickSort, the work is done in the Divide step, and basically no work is done in the Combine step!
The QuickSort algorithm does the same thing as Merge Sort: Divide, Conquer, and Combine, but in my personal opinion, QuickSort is a little more confusing than Merge Sort, so I’m going to break down what happens in each step:
- Select an element inside of the array, the element you select should be either the first or last element in the array. This element is commonly referred to as the pivot.
- Rearrange the elements of the array so that all of the elements smaller than the pivot are to the left and all the elements greater than the pivot are to the right. This step is called partitioning. It is important to note that if an element is equal to the pivot it doesn’t matter which side of the array it is on.
- Repeat steps 2 and 3 individually for the left and right sides of the pivot until the array is sorted.
Heres a visual:
Now that we’ve got a decent understanding of what the QuickSort algorithm is all about, let’s take a look at how we can implement this using JavaScript!
Partition()
First off, we’re going to create a partition() function to take care of our partitioning step in the algorithm:
In the function above, 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 pivotIndex.
In the last step, we swap the pivot (which in our case is the last element) with the pivotIndex. In the end, our pivot element ends up in the “middle”, with elements less than the pivotIndex to the left and elements more than the pivotIndex to the right.
QuickSort()
Now that we’ve got our partition() function, we now have to apply it to our recursive algorithm so that we repeat the process until the array is sorted. Here I will write a quickSort() function to accomplish this task:
Here, we start by partitioning the array. After that we continue to partition both the left and right subarrays. We repeat the process as long as the method doesn’t receive and empty array or an array that only has one element. This is because an array that is empty or an array that only has one element is considered sorted.
Now let’s test it out!
After writing this out you should have a sorted array in your console that looks like this:
Amazing!
Thanks for taking the time to read this article, and hopefully you learned something about the QuickSort algorithm and the Divide and Conquer paradigm. I will continue my programming journey by learning new paradigms and algorithms, and I hope you do too! Happy coding!
