In my last article, I chose to dive in to the “Divide and Conquer” algorithmic paradigm, and what I found was quite interesting!
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 is similar to Merge Sort, but there are a few differences. Merge Sort is broken down into 3 steps:
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:
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.
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:
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!
Introduction Sorting refers to arranging items of a list in a specific order (numerical or alphabetic). Sorting is…