This content originally appeared on DEV Community and was authored by Emmanuel Ayinde
Quicksort is one of the fastest sorting algorithms. It takes an array of values, chooses one of the values as the 'pivot' element, and moves the other values so that lower values are on the left of the pivot element, and higher values are on the right of it.
Quick Sort stands as one of the most elegant and efficient sorting algorithms in the world of algorithms. Unlike simpler algorithms like Bubble Sort or Selection Sort, Quick Sort employs a sophisticated divide-and-conquer strategy that makes it significantly faster in practice. While Merge Sort also uses divide-and-conquer, Quick Sort's unique partitioning approach often leads to better performance and memory usage.
Average Time Complexity: O(n log n)
Worst Case Time Complexity: O(n²)
Space Complexity: O(log n)
Table of Contents
- What is quick sort algorithm
-
How does quick sort work
- Time Complexity
- Space Complexity
- JavaScript Implementation
- Conclusion
What is Quick Sort Algorithm
Quick Sort is a highly efficient sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. Unlike Merge Sort, which divides first and combines later, Quick Sort does its sorting during the partitioning process.
Consider this comparison with other sorting algorithms:
| Algorithm | Time Complexity (Average) | Space Complexity | In-Place? |
|---|---|---|---|
| Quick Sort | O(n log n) | O(log n) | Yes |
| Merge Sort | O(n log n) | O(n) | No |
| Bubble Sort | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(1) | Yes |
| Heap Sort | O(n log n) | O(1) | Yes |
How does quick sort work?
Before we dive into the JavaScript implementation of quick sort algorithms, let's take a step-by-step approach to understand how the algorithm works by manually sorting a simple array of numbers with just four simple steps.
Quick sort can be broken down into four simple steps:
- Choose a pivot element from the array. This element could be the first, the last, the middle or even a random element from the list/array.
- Rearrange the array so that all elements less than the pivot are on the left, and all elements greater are on the right.
- Swap the pivot element with the first element of the greater values, so that the pivot is in the middle.
- Recursively apply the same operations to the sub-arrays on the left and right of the pivot.
Let's apply these steps to a real array. Shall we?
Initial Array: [3, 6, 2, 7, 1]
Step 1: Choose a Pivot
- We choose the last element as the pivot for simplicity.
-
Pivot =
1
Step 2: Rearrange Array Around Pivot
- Rearrange so that all elements less than the pivot (
1) are on the left and all elements greater are on the right. - As we go through each element:
-
3(greater than1) → stays on the right. -
6(greater than1) → stays on the right. -
2(greater than1) → stays on the right. -
7(greater than1) → stays on the right.
-
-
Rearranged Array:
[1, 6, 2, 7, 3]
Step 3: Swap Pivot to its Correct Position
- Swap the pivot (
1) with the first element greater than it, which is6. -
Array after swapping:
[1, 3, 2, 7, 6] - Now,
1is in the correct position (index 0).
Step 4: Recursive Quick Sort on Sub-arrays
-
Left Sub-array:
[](no elements left of1, so nothing to sort here) -
Right Sub-array:
[3, 2, 7, 6]
Sorting the Right Sub-array [3, 2, 7, 6] recursively
Step 1: Choose a Pivot
-
Pivot =
6(last element)
Step 2: Rearrange Array Around Pivot
- Arrange elements less than
6to the left and greater ones to the right:-
3(less than6) → stays on the left. -
2(less than6) → stays on the left. -
7(greater than6) → stays on the right.
-
-
Rearranged Array:
[3, 2, 6, 7]
Step 3: Swap Pivot to Its Correct Position
-
6is already in the correct position (index 2). -
Array:
[1, 3, 2, 6, 7]
Step 4: Recursive Quick Sort on Sub-arrays
-
Left Sub-array:
[3, 2] -
Right Sub-array:
[7](single element, no sorting needed)
Sorting the Left Sub-array [3, 2]
Step 1: Choose a Pivot
-
Pivot =
2(last element)
Step 2: Rearrange Array Around Pivot
- Rearrange so elements less than
2are on the left:-
3(greater than2) → stays on the right.
-
-
Rearranged Array:
[2, 3]
Step 3: Swap Pivot to Its Correct Position
-
2is already in the correct position (index 1). -
Array:
[1, 2, 3, 6, 7]
Step 4: Recursive Quick Sort on Sub-arrays
-
Left Sub-array:
[](no elements) -
Right Sub-array:
[3](single element, no sorting needed)
Final Sorted Array
After sorting all the sub-arrays, we get the final sorted array:
Sorted Array: [1, 2, 3, 6, 7]
Below is the best illustration of how this works in real life:
Time Complexity
Quick Sort's time complexity varies based on pivot selection:
-
Best Case (O(n log n)):
- Occurs when the pivot always divides the array into equal halves
- Similar to Merge Sort's performance
-
Average Case (O(n log n)):
- Most practical scenarios
- Better than Merge Sort due to better cache utilization
-
Worst Case (O(n²)):
- Occurs with already sorted arrays and poor pivot selection
- Can be avoided with good pivot selection strategies
Space Complexity
Quick Sort's space complexity is O(log n) due to:
- Recursive call stack depth
- In-place partitioning (unlike Merge Sort's O(n) extra space)
- Better memory efficiency compared to Merge Sort
JavaScript Implementation
function quickSort(arr) {
// Base case: arrays with length 0 or 1 are already sorted
if (arr.length <= 1) return arr;
// Helper function to swap elements
const swap = (i, j) => {
[arr[i], arr[j]] = [arr[j], arr[i]];
};
// Partition function using Lomuto's partition scheme
function partition(low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(i, j);
}
}
swap(i + 1, high);
return i + 1;
}
// Main quickSort function implementation
function quickSortHelper(low, high) {
if (low < high) {
const pivotIndex = partition(low, high);
quickSortHelper(low, pivotIndex - 1); // Sort left side
quickSortHelper(pivotIndex + 1, high); // Sort right side
}
}
quickSortHelper(0, arr.length - 1);
return arr;
}
Conclusion
Quick Sort is a popular choice due to its efficiency and in-place sorting. It outperforms simpler algorithms like Bubble Sort and Selection Sort with its O(n log n) average-case performance and low space complexity.
Key takeaways:
- Choose pivot selection strategy carefully
- Consider input characteristics when deciding between Quick Sort and other algorithms
- Use randomized pivot selection for better average-case performance
Stay Updated and Connected
To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:
Stay tuned and happy coding 👨💻🚀
This content originally appeared on DEV Community and was authored by Emmanuel Ayinde
Emmanuel Ayinde | Sciencx (2024-11-06T21:23:05+00:00) Cracking Quick Sort algorithm: From Theory to Practice in Minutes. Retrieved from https://www.scien.cx/2024/11/06/cracking-quick-sort-algorithm-from-theory-to-practice-in-minutes/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.