Algorithms: Quicksort
Algorithms and Data Structures From Zero to Hero
In this blog, we will be discussing the quicksort algorithm, a popular sorting algorithm that is known for its efficiency and effectiveness. Quicksort is a divide and conquer algorithm, which means that it works by dividing the unsorted list into smaller sub-lists and then sorting each sub-list independently before combining them back into a single, sorted list.
We will first explain the basic concept behind quicksort and how it works, and then we will look at an example of how to implement quicksort in JavaScript. We will also discuss the time complexity of quicksort and why it is considered to be a fast and effective sorting algorithm.
By the end of this blog, you should have a good understanding of what quicksort is and how it can be used to efficiently and effectively sort large lists of data.
To follow this article you need to understand the following topics:
Divide & conquer
Divide and conquer is a problem-solving approach that involves breaking a large problem down into smaller, more manageable sub-problems, solving each sub-problem independently, and then combining the solutions to the sub-problems to solve the larger problem.
One way to think about divide and conquer is to imagine that you have a large, complex puzzle that you need to solve. Instead of trying to solve the entire puzzle at once, which might be overwhelming, you divide the puzzle into smaller, easier to solve pieces. You then work on each piece independently, solving each one as you go. Once you have solved all of the smaller pieces, you can then put them all together to solve the larger puzzle.
In this way, divide and conquer is similar to the saying “divide and conquer,” which means to split something into smaller pieces in order to make it easier to manage or control. By breaking a large problem down into smaller, more manageable sub-problems, you can make it easier to solve and more likely to succeed.
Quicksort
Quicksort is a sorting algorithm. It’s much faster than selection sort and is frequently used in real life.
Let’s use quicksort to sort an array. What’s the simplest array that a sorting algorithm can handle? Well, some arrays don’t need to be sorted at all.
[ ] ← EMTY ARRAY
[14] ← ARRAY WITH ONE ELEMENT
Empty arrays and arrays with just one element will be the base case. You can just return those arrays as is — there’s nothing to sort:
function quickSort(arr) {
if (arr.length <= 1) {
return arr
}Let’s look at bigger arrays. An array with two elements is pretty easy to sort, too.
[1, 7] ← check if first element is smaller than the second if it isn’t, swap them.
What about an array of three elements?
[13, 7, 1]
Remember, you’re using D&Q. So you want to break down this array until you’re at the base case. Here’s how quicksort works.
First pick an element from the array. This element is called the pivot.
pivot → 13
Now find the elements smaller than pivot and the elements larger than pivot.
smaller → [7, 1]
larger → []
This called partitioning. Now you have
- A sub-array of all the numbers less than the pivot
- The pivot
- A sub-array of all the numbers greater than the pivot
The two sub-array aren’t sorted. They’re just partitioned. But if they were sorted, then sorting the whole array would be pretty easy.
[1, 7] <13> [ ]
If the sub-arrays are sorted, then you can combine the whole thing like this — left array + pivot + right array — and you get a sorted array. In this case, it’s [1, 7] + [13] + [ ] = [1, 7, 13], which is a sorted array.
How do you sort the sub-arrays? Well, the quicksort base case already knows how to sort arrays of two elements (the left sub-array) and empty arrays (the right sub-array). So if you call quicksort on the two sub-arrays and then combine the results, you get a sorted array!
quickSort([7, 1]) + [13] + quickSort([])
> [1, 7, 13] <------ A sorted arrayThis works with any element as the pivot. So you can sort an array of N elements.
Inductive proof
You just got sneak peak into inductive proofs! Inductive proofs are one way to prove that your algorithm works. Each inductive proof has two steps: the base case and the inductive case. Sound familiar? For example, suppose I want to prove that I can climb to the top of a ladder. In the inductive case, if my legs are on a rung, I can put my legs on the next rung. So if I’m on rung 2, I can climb to rung 3. That’s the inductive case. For the base case, I’ll say that my legs are on rung 1. Therefore, I can climb the entire ladder, going up one rung at a time.
You use similar reasoning for quicksort. In the base case, I showed that the algorithm works for the base case: arrays of size 0 and 1. In the inductive case, I showed that if quicksort works for an arrays of size 1, it will work for an array of size 2, 3… 1+N.
Time Complexity
- Best / average case: O ( n . log ( n ) ) in most balanced scenarios, when the generated partitions have nearly equal elements. Thus for a balanced case, the depth of the recursion tree is log2 ( n ) and the reordering at each recursion level takes O ( n ) time.
Thus giving the time complexity O ( n . log ( n ) ) - Worst case: O ( n2 ) when the array is already sorted, the pivot element will require n comparisons to deduce that it remains in its position at the end. Furthermore, the first partition would be empty, but the second partition will have (n-1) elements. Similarly, the pivot in the second partition will need (n-1) comparisons to deduce that it remains in its position at the end and so on. Consequently there will be a total of F(n) = n + (n-1) + (n-2) + .. + 2 + 1 comparisons. Thus giving a worst-case time complexity of O ( n2 ).
Example code listing
function quickSort(arr) {
// base case: arrays with 0 or 1 element are already "sorted"
if (arr.length <= 1) {
return arr
}
const pivot = arr[0]
// partition the list into two sub-lists
let left = []
let right = []
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
// recursively sort the two sub-lists
left = quickSort(left)
right = quickSort(right)
// combine the sorted sub-lists back into a single, sorted list
return left.concat(pivot, right)
}Summary
In conclusion, the quicksort algorithm is a popular and effective way to sort large lists of data. It is a divide and conquer algorithm that works by dividing the unsorted list into smaller sub-lists and then sorting each sub-list independently before combining them back into a single, sorted list.
Quicksort is known for its efficiency because it has a time complexity of O(n log n) on average, which is much faster than other sorting algorithms with a similar time complexity, such as mergesort. It is also relatively easy to implement, which makes it a good choice for many different applications.
In this blog, we have discussed the basic concept behind quicksort and provided an example of how to implement it in JavaScript. We have also discussed the time complexity of quicksort and why it is considered to be a fast and effective sorting algorithm.
Overall, quicksort is a powerful and useful algorithm that can be used to quickly and effectively sort large lists of data.
