Quick Sort - “Divide and Conquer” in Sorting
Quick Sort is a “lightning-fast” and extremely efficient sorting algorithm. It is one of the most widely used algorithms today, especially in applications that require handling large amounts of data. Quick Sort is based on the “divide and conquer” principle – a powerful strategy that helps solve complex problems by breaking them down into smaller, simpler subproblems, solving each subproblem, and then combining them to obtain the final result.
How Does Quick Sort Work?
Basically, Quick Sort works as follows:
- Choose a “Pivot”: First, the algorithm selects an element in the array to be the “pivot.”
- Partitioning: Next, the remaining elements in the array are divided into two groups:
- Group 1: Contains elements smaller than the pivot.
- Group 2: Contains elements greater than or equal to the pivot.
- Recursion: The algorithm repeats the process (choosing a pivot and partitioning) for each group (group 1 and group 2) recursively until each group contains only one element or no elements at all. At that point, the array is sorted.
Implementing Quick Sort in JavaScript
To understand better, let’s look at how to implement Quick Sort in JavaScript:
function quickSort(arr) {
if (arr.length <= 1) {
return arr; // If the array has 0 or 1 element, it is already sorted
}
const pivot = arr[arr.length - 1]; // Choose the last element as the pivot (could choose another element)
const left = []; // Sub-array containing elements smaller than the pivot
const right = []; // Sub-array containing elements greater than or equal to the pivot
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// Recursively sort the sub-arrays and concatenate them with the pivot in between
return [...quickSort(left), pivot, ...quickSort(right)];
}
// Test
const array = [7, 2, 1, 6, 8, 5, 3, 4];
const sortedArray = quickSort(array);
console.log(sortedArray); // Result: [1, 2, 3, 4, 5, 6, 7, 8]
Code Explanation:
- The
quickSort(arr)
function takes an arrayarr
that needs to be sorted. - If the array has 0 or 1 elements, it is already sorted, so return it.
- The last element of the array is chosen as the pivot.
- Two sub-arrays,
left
andright
, are created to store elements smaller than and greater than or equal to the pivot, respectively. - A
for
loop is used to iterate through the array (excluding the pivot) and place each element into eitherleft
orright
. - The function recursively calls
quickSort
onleft
andright
, and then concatenates the results with the pivot in the middle using the spread syntax...
.
Customization and Application
With the above implementation, you can now sort arrays of integers in ascending order. However, you can easily modify the code to sort in descending order or to sort objects based on a specific property.
Conclusion:
Quick Sort is a powerful tool that every programmer should know. With an average time complexity of O(n log n), Quick Sort is well-suited for applications that handle large amounts of data. I hope this article helped you understand the Quick Sort algorithm and how to implement it in JavaScript. Try applying it to your projects and optimize your sorting performance!
P.S. You can also practice with the Javascript Quick Sort solution :<