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)
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 |
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]
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:
Quick Sort's time complexity varies based on pivot selection:
Best Case (O(n log n)):
Average Case (O(n log n)):
Worst Case (O(n²)):
Quick Sort's space complexity is O(log n) due to:
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;
}
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:
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 ???
The above is the detailed content of Cracking Quick Sort algorithm: From Theory to Practice in Minutes. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
