Quick Sort is one of the most popular and efficient sorting algorithms. It uses the divide and conquer strategy, similar to Merge Sort, but it often outperforms Merge Sort in practice due to its in-place sorting nature. In this blog post, we will explore how to implement Quick Sort in JavaScript, discuss its time and space complexities, and walk through the algorithm step-by-step.
What is Quick Sort?
Quick Sort selects a “pivot” element from the array and partitions the other elements into two sub-arrays: one with elements smaller than the pivot and one with elements greater than the pivot. The pivot is then placed in its correct position in the sorted array, and the process is recursively applied to the sub-arrays.
Pseudocode for Quick Sort
Here’s the basic pseudocode for Quick Sort:
procedure quickSort(arr, low, high) if low < high then pivotIndex = partition(arr, low, high) // Step 1: Partition the array quickSort(arr, low, pivotIndex - 1) // Step 2: Recursively sort the left sub-array quickSort(arr, pivotIndex + 1, high) // Step 3: Recursively sort the right sub-array procedure partition(arr, low, high) pivot = arr[high] // Step 4: Choose the pivot (last element in the array) i = low - 1 // Step 5: Initialize i to point to the element before the sub-array for j = low to high - 1 // Step 6: Iterate over the array from low to high - 1 if arr[j] <= pivot then i = i + 1 // Step 7: Increment i swap arr[i] with arr[j] // Step 8: Swap arr[i] and arr[j] (elements less than the pivot) swap arr[i + 1] with arr[high] // Step 9: Place the pivot in its correct position return i + 1 // Step 10: Return the pivot index
Step-by-Step Breakdown of the Pseudocode
Quick Sort Function (Main Recursive Function)
- Base Condition:
- The function checks if
low
is less thanhigh
. If not, it means the array or sub-array has only one or zero elements, which is already sorted, so we stop. - This condition ensures the recursive function terminates when the sub-array size becomes 1 or 0.
- The function checks if
- Partition the Array:
- The
partition()
function is called to rearrange the elements in the array so that all elements smaller than the pivot are on the left and all elements larger are on the right. The pivot is placed in its correct position in the sorted array. - After the partitioning step, the array is divided into two sections: the left and right of the pivot.
- The
- Recursively Sort the Left and Right Sub-arrays:
- The
quickSort()
function is called recursively on the left sub-array (low
topivotIndex - 1
), which contains elements smaller than the pivot. - It is also called on the right sub-array (
pivotIndex + 1
tohigh
), which contains elements larger than the pivot. - This process continues until all sub-arrays are fully sorted.
- The
Partition Function (Rearranges the Array Around the Pivot)
- Select the Pivot:
- The pivot is usually selected as the last element (
arr[high]
). The goal is to place this pivot in its correct sorted position.
- The pivot is usually selected as the last element (
- Initialize the Index for Smaller Elements (
i
):- Set
i
tolow - 1
, which points to the position before the first element of the sub-array. This is important becausei
will track the “boundary” between elements smaller than the pivot and those larger than the pivot.
- Set
- Iterate Over the Array (
j
Loop):- A loop runs from
low
tohigh - 1
(excluding the pivot itself). - We compare each element in this loop to the pivot.
- A loop runs from
- Check If the Current Element is Smaller or Equal to the Pivot:
- If the element at
arr[j]
is smaller than or equal to the pivot, it means it should be on the left side of the pivot. - We increment
i
to include the current element in the “smaller elements” section.
- If the element at
- Swap Elements to Place Smaller Elements on the Left:
- Swap
arr[i]
witharr[j]
. This ensures that all elements less than or equal to the pivot end up on the left side of the pivot.
- Swap
- Place the Pivot in the Correct Position:
- After the loop ends, swap
arr[i + 1]
with the pivot (arr[high]
). This places the pivot in its correct position in the sorted array, as all elements to its left are smaller, and all elements to its right are larger.
- After the loop ends, swap
- Return the Pivot Index:
- Finally, return
i + 1
as the new pivot index. This index will further divide the array into sub-arrays for recursive sorting.
Time Complexity of Quick Sort
- Best Case: O(n log n) – This occurs when the pivot divides the array into two nearly equal halves, leading to logarithmic recursive depth.
- Average Case: O(n log n) – Quick Sort performs O(n log n) operations on average, making it highly efficient for most datasets.
- Worst Case: O(n²) – The worst-case scenario occurs when the pivot repeatedly selects the smallest or largest element, leading to unbalanced partitions. This can happen if the array is already sorted.
Space Complexity of Quick Sort
- Space Complexity: O(log n) – Quick Sort uses recursive calls, which take up stack space. The recursion depth is proportional to the logarithm of the array size in the best and average cases.
JavaScript Implementation of Quick Sort
Here’s how you can implement Quick Sort in JavaScript:
// Partition function to place the pivot in the correct position function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap arr[i] and arr[j] } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Place pivot in correct position return i + 1; } // Recursive Quick Sort function function quickSort(arr, low = 0, high = arr.length - 1) { if (low < high) { const pivotIndex = partition(arr, low, high); // Recursively sort elements before and after the partition quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } return arr; } // Example usage const arr = [10, 80, 30, 90, 40, 50, 70]; console.log("Initial array:", arr); console.log("Sorted array:", quickSort(arr));
Output:
Initial array: [ 10, 80, 30, 90, 40, 50, 70 ] Sorted array: [ 10, 30, 40, 50, 70, 80, 90 ]
Step-by-Step Walkthrough of Quick Sort
Let’s walk through Quick Sort using the array [10, 80, 30, 90, 40, 50, 70]
.
Step 1: First Partitioning
- Select
70
as the pivot. - Rearrange the array so that elements smaller than
70
are on the left and elements larger are on the right:- Compare
10
with70
(no swap, move to next). - Compare
80
with70
(no swap). - Compare
30
with70
(swap80
and30
). - Compare
90
with70
(no swap). - Compare
40
with70
(swap80
and40
). - Compare
50
with70
(swap80
and50
).
- Compare
- Place
70
in its correct position, swapping it with80
. - Array after the first partition:
[10, 30, 40, 50, 70, 90, 80]
Step 2: Sort Left Sub-array
- Recursively apply Quick Sort to the left sub-array
[10, 30, 40, 50]
using the same logic. - The left sub-array is already sorted after one recursive call:
- Array after sorting left sub-array:
[10, 30, 40, 50]
- Array after sorting left sub-array:
Step 3: Sort Right Sub-array
- Now apply Quick Sort to the right sub-array
[90, 80]
. - Select
80
as the pivot and swap it with90
:- Array after sorting right sub-array:
[80, 90]
- Array after sorting right sub-array:
Step 4: Final Array
- After recursively sorting the left and right sub-arrays, the final sorted array is:
- Sorted Array:
[10, 30, 40, 50, 70, 80, 90]
- Sorted Array:
To see how Selection Sort works in practice, go to the Sorting Algorithm Visualizer!
Pros and Cons of Using Quick Sort
Pros:
- Efficient for Large Datasets: Quick Sort has an average-case time complexity of O(n log n), making it one of the fastest sorting algorithms.
- In-Place Sorting: Unlike Merge Sort, Quick Sort sorts the array in place, so it doesn’t require additional memory.
- Widely Used: Quick Sort is the go-to algorithm for many practical implementations due to its speed and efficiency.
Cons:
- Worst-Case Performance: In the worst case, Quick Sort’s time complexity degrades to O(n²) when the pivot selection is poor (e.g., choosing the smallest or largest element).
- Not Stable: Quick Sort is not a stable sorting algorithm, meaning it does not preserve the relative order of equal elements.
When to Use Quick Sort
Quick Sort is ideal when:
- You need a fast, in-place sorting algorithm: With O(n log n) average-case time complexity and in-place sorting, Quick Sort is great for large datasets where memory usage matters.
- Random or unsorted data: Quick Sort works well with data that has no clear ordering, as its performance is generally consistent.
- You need general-purpose sorting: Quick Sort is widely used in practical applications because of its speed and versatility.
However, for datasets that are already sorted or nearly sorted, Merge Sort or Insertion Sort might be a better choice due to Quick Sort’s poor performance in its worst case.
Conclusion
Quick Sort is a fast and efficient sorting algorithm, but optimizing it for various scenarios can further improve its performance. Here are some key optimizations:
- Median-of-three pivot selection: Using the median of the first, middle, and last elements as the pivot helps ensure more balanced partitions and avoids worst-case scenarios.
- Insertion Sort for small sub-arrays: Switching to Insertion Sort for small sub-arrays reduces overhead and speeds up sorting.
- Tail call optimization: Limits recursion depth and prevents stack overflow by sorting larger sub-arrays iteratively.
- Three-way partitioning: Handles arrays with many duplicates more efficiently by reducing unnecessary swaps and comparisons.
- Hybrid algorithms (IntroSort): Switching to algorithms like Heap Sort if the recursion depth gets too deep ensures performance doesn’t degrade to O(n²).
These optimizations make Quick Sort faster and more reliable, especially for large datasets or special cases where the default version may struggle.
Congratulations on reading to the end of the tutorial!
Read the following articles to learn how to implement Quick Sort:
In Python – How to do Quick Sort in Python
In C++ – How to Do Quick Sort in C++
Have fun and happy researching!
Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.