Quick Sort Explained: Partitioning, Recursion & Time Complexity
A practical explanation of Quick Sort using the first element as the pivot, with JavaScript implementation and a visual walkthrough of the partition process.
Sorting an array looks simple until you start asking a more interesting question:
This is where Quick Sort becomes interesting.
Quick Sort doesn't try to find the smallest element one by one. Instead, it chooses an element called a pivot and rearranges the array so that elements smaller than the pivot move toward one side and elements greater than the pivot move toward the other.
Once the pivot reaches its correct position, the same process is repeated on the left and right portions of the array.
The algorithm sounds simple.
The interesting part is how the partitioning actually works.
Quick Sort in One Picture
At a high level, Quick Sort follows three steps:
Pick an element from the current range.
Move smaller and larger elements to their appropriate sides.
Recursively sort the two sides.
In this implementation, we'll always choose the first element of the current range as the pivot.
Let's Start With an Example
Consider this array:
We start with the complete array.
Since we're using the first element as the pivot:
Now our job is to rearrange the array so that values smaller than 2 end up on the left and values greater than 2 end up on the right.
In this particular array, there is only one value smaller than 2:
Once partitioning finishes, the pivot will be placed between those two groups.
Understanding the Partition Function
The most important part of Quick Sort is not the recursion.
It is the partition function.
Our partition function receives:
Here:
- arr is the array.
- low is the beginning of the current section.
- high is the end of the current section.
The first thing we do is select the pivot:
Because we're using the first element, the pivot is simply:
Now We Need Two Pointers
This is where the algorithm becomes interesting.
We use two pointers:
Starts at the pivot and moves toward the right.
Starts at the end and moves toward the left.
In code:
let right = high;
You can think of the pointers as two people searching from opposite directions.
What Does the Left Pointer Look For?
The left pointer searches for an element that is greater than the pivot.
Why?
Because a value greater than the pivot doesn't belong on the left side. We want to eventually move it toward the right.
left++;
}
As long as the current value is less than or equal to the pivot, we keep moving.
The pointer stops when it finds a value that is greater than the pivot.
Find something that belongs on the right side.
What Does the Right Pointer Look For?
The right pointer does the opposite.
It searches for an element that is smaller than the pivot.
right--;
}
As long as the current value is greater than or equal to the pivot, the pointer moves left.
It stops when it finds a value that is smaller than the pivot.
Find something that belongs on the left side.
The Key Idea Behind the Swap
Now both pointers have found something useful.
The left pointer found an element that is too large for the left side.
The right pointer found an element that is too small for the right side.
So we swap them.
This is the heart of the partition operation.
We continue doing this until the two pointers meet or cross.
Then Comes the Important Pivot Swap
Once the two pointers are finished, we still haven't placed the pivot in its final position.
Remember that our pivot is still sitting at:
The right pointer has now stopped at the position where the pivot belongs.
So we perform:
This final swap is what puts the pivot into its correct sorted position.
Every element to the left of the pivot is smaller than or equal to it, and every element to the right is greater than or equal to it.
Quick Sort's Secret: Recursion
Once the pivot is in its correct position, we have solved one part of the problem.
We don't need to move that pivot again.
Instead, we divide the problem into two smaller problems.
↓
Quick Sort left Quick Sort right
That's exactly what these two lines do:
quickSort(arr, pivotIndex + 1, high);
The same partitioning process keeps happening until each section contains zero or one element.
Visualizing the Recursion
You can imagine Quick Sort breaking the array down like this:
↓
[1] [2] [5, 6, 3, 4, 7, 9, 8]
↓
[3, 4] [5] [6, 7, 9, 8]
↓
[6] [7] [8] [9]
Eventually, every element reaches a position where there is nothing left to sort around it.
When Does the Recursion Stop?
Every recursive algorithm needs a base case.
For Quick Sort, the base case is very simple:
return;
}
Why?
Because an array section containing zero or one element is already sorted.
1 element → already sorted
The Complete JavaScript Implementation
Putting everything together, the implementation looks like this:
const arr = [2, 5, 6, 3, 1, 4, 7, 9, 8];
function partition(arr, low, high) {
const pivot = arr[low];
let left = low;
let right = high;
while (left < right) {
// Find an element greater than the pivot
while (left < high && arr[left] <= pivot) {
left++;
}
// Find an element smaller than the pivot
while (right > low && arr[right] >= pivot) {
right--;
}
// Swap the elements
if (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
}
}
// Put pivot in its correct position
[arr[low], arr[right]] = [arr[right], arr[low]];
return right;
}
function quickSort(arr, low, high) {
// Base case: zero or one element
if (low >= high) {
return;
}
const pivotIndex = partition(arr, low, high);
// Sort left side of pivot
quickSort(arr, low, pivotIndex - 1);
// Sort right side of pivot
quickSort(arr, pivotIndex + 1, high);
}
quickSort(arr, 0, arr.length - 1);
console.log(arr);Time Complexity: Where Quick Sort Gets Interesting
Quick Sort doesn't always divide the array equally.
And that is exactly why its time complexity depends heavily on the pivot.
Best Case: O(n log n)
The best situation occurs when the pivot divides the array into roughly equal halves every time.
↓
n/2 n/2
↓ ↓
n/4 n/4 n/4 n/4
↓
...
Each level processes approximately n elements, and there are roughly log n levels.
Therefore:
Average Case: O(n log n)
Even when the partitions aren't perfectly balanced, Quick Sort generally performs very well on average.
With a reasonably good pivot selection strategy, the expected complexity is:
Worst Case: O(n²)
Here's where our choice of the first element as the pivot becomes important.
Imagine the array is already sorted:
We choose 1 as the pivot.
There are no elements smaller than 1, so the pivot ends up at the beginning.
Now Quick Sort has to process:
Instead of dividing the problem in half, we're effectively removing only one element at each step.
So Why Not Just Always Use the First Element?
This is the obvious question.
If choosing the first element works and keeps the implementation simple, why do many implementations use a random pivot?
The answer isn't that the first-element approach is wrong.
It's that the input data can make its performance predictable.
If you know your data is already sorted, reverse sorted, or has a structure that repeatedly produces poor partitions, always choosing the first element can lead to the worst case.
Randomizing the pivot makes it much harder for a particular input arrangement to consistently produce terrible partitions.
Simple, predictable, easy to understand.
``` Random pivot
Reduces the likelihood of repeatedly getting highly unbalanced partitions. ```
For learning Quick Sort, however, using the first element is an excellent way to understand the algorithm because the partition logic is easier to reason about.
What About Space Complexity?
Quick Sort is an in-place sorting algorithm in this implementation because we're rearranging elements inside the original array instead of creating separate arrays for every partition.
However, recursion still consumes stack space.
| Case | Time | Recursion Stack |
|---|---|---|
| Best | O(n log n) | O(log n) |
| Average | O(n log n) | O(log n) |
| Worst | O(n²) | O(n) |
Quick Sort vs Merge Sort
Quick Sort is often compared with Merge Sort because both have an average time complexity of O(n log n).
| Feature | Quick Sort | Merge Sort |
|---|---|---|
| Average time | O(n log n) | O(n log n) |
| Worst case | O(n²) | O(n log n) |
| Extra array memory | Low | Higher |
| In-place | Yes | Typically no |
| Main idea | Partition around pivot | Split and merge |
The Easiest Way to Remember Quick Sort
If you forget the implementation details, remember these three questions:
1. What is my pivot?
In our implementation: the first element.
2. What is partition doing?
Finding misplaced elements on both sides and swapping them.
3. What happens after partition?
The pivot is in its correct position, so recursively sort the left and right sides.
Final Thoughts
Quick Sort is a great example of how an algorithm can look complicated in code while being surprisingly simple at the conceptual level.
We choose a pivot, use two pointers to find misplaced elements, swap them, place the pivot in its correct position, and repeat the same process on the two smaller sections.
The implementation above deliberately uses the first element as the pivot. That makes the algorithm easy to understand and is a good starting point for learning partitioning and recursion.
But it also teaches an important lesson about algorithms:
How you choose the pivot can determine whether Quick Sort behaves like O(n log n) or falls all the way to O(n²).
Once you understand that trade-off, you're no longer just memorizing Quick Sort.
You're understanding why the algorithm behaves the way it does.
Quick Takeaways
- Quick Sort uses a pivot to partition an array.
- This implementation chooses the first element as the pivot.
- The left pointer searches for an element greater than the pivot.
- The right pointer searches for an element smaller than the pivot.
- Those misplaced elements are swapped.
- The pivot is finally placed in its correct position.
- Quick Sort recursively sorts the two sides.
- Average and best-case time complexity is O(n log n).
- Worst-case time complexity is O(n²).
- Pivot selection can significantly affect performance.
Tags: Quick Sort, Quick Sort JavaScript, Sorting Algorithms, Algorithms, Data Structures, JavaScript Algorithms, DSA, Recursion, Partition Algorithm, Time Complexity, Space Complexity, Coding Interview, Software Development
No comments:
Post a Comment