Sorting Things Out: A Comprehensive Guide to Quick Sort in JavaScript
Have you ever found yourself with a pile of items that needed to be organized, but didn't know where to start? Sorting algorithms, like Quick Sort, can help us take that chaotic jumble and put it into a neat and orderly arrangement. In this article, we'll dive into Quick Sort and how it works in JavaScript, as well as explore some examples of where it can be put to use.
What is Quick Sort?
Quick Sort is an efficient sorting algorithm that works by selecting a "pivot" element from an array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. It then repeats this process for each sub-array until all elements are sorted.
Here's the basic pseudocode for Quick Sort:
function quickSort(array) {
// base case: if the array has fewer than 2 elements, return it (already sorted)
if (array.length < 2) {
return array;
}
// choose a pivot element
var pivotIndex = Math.floor(array.length / 2);
var pivot = array[pivotIndex];
// create left and right arrays
var left = [];
var right = [];
// partition the rest of the array into left and right sub-arrays
for (var i = 0; i < array.length; i++) {
if (i !== pivotIndex) {
if (array[i] < pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
}
// recursive call on left and right sub-arrays
return quickSort(left).concat(pivot, quickSort(right));
}
The pivot element is typically chosen as the middle element of the array, but it can also be chosen randomly or based on other criteria. The key is to choose a pivot that will split the array into two relatively even sub-arrays, which helps ensure that Quick Sort runs efficiently.
How Quick Sort Works in Practice
To get a better understanding of how Quick Sort works, let's walk through an example using the above pseudocode.
Suppose we have the following array of integers that we want to sort in ascending order:
[5, 3, 1, 8, 4, 7, 2, 6]
The first thing we do is check the base case: if the array has fewer than 2 elements, return it (already sorted). Since our array has more than 1 element, we proceed to the next step and choose a pivot element. In this case, we'll choose the middle element, which is 5.
Next, we create two empty arrays, left and right, and partition the rest of the elements into these arrays based on whether they are less than or greater than the pivot. Our left array will contain the elements that are less than 5, and our right array will contain the elements that are greater than 5.
left: [3, 1, 4, 2]
pivot: 5
right: [8, 7, 6]
Now we make a recursive call on the left and right sub-arrays, using the same Quick Sort algorithm. This will repeat until we reach the base case of having an array with fewer than 2 elements, at which point the array will be returned as sorted.
Here's what the recursive calls would look like for our example array:
quickSort([5, 3, 1, 8, 4, 7, 2, 6])
quickSort([3, 1, 4, 2])
quickSort([1, 2])
return [1, 2]
quickSort([4])
return [4]
quickSort([8, 7, 6])
quickSort([6])
return [6]
quickSort([8, 7])
quickSort([7])
return [7]
quickSort([8])
return [8]
Finally, we concatenate the sorted sub-arrays and pivot element to get our fully sorted array:
[1, 2, 3, 4, 5, 6, 7, 8]
Example
Now that we have a better understanding of how Quick Sort works, let's explore some examples of where it can be put to use.
Sorting a list of names alphabetically:
function sortNames(names) {
// QuickSort is without a specific condition
return quickSort(names);
}
console.log(sortNames(["Alice", "Bob", "Eve", "Charlie", "Dave"]));
// Output: ["Alice", "Bob", "Charlie", "Dave", "Eve"]
Sorting an array of objects by a specific property:
function quickSort(array, condition = (a, b) => a < b) {
// base case: if the array has fewer than 2 elements, return it (already sorted)
if (array.length < 2) {
return array;
}
// choose a pivot element
var pivotIndex = Math.floor(array.length / 2);
var pivot = array[pivotIndex];
// create left and right arrays
var left = [];
var right = [];
// partition the rest of the array into left and right sub-arrays
for (var i = 0; i < array.length; i++) {
if (i !== pivotIndex) {
if (condition(array[i], pivot)) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
}
// recursive call on left and right sub-arrays
return quickSort(left).concat(pivot, quickSort(right));
}
function sortByAge(people) {
return quickSort(people, (a, b) => a.age < b.age);
}
console.log(
sortByAge([
{ name: "Alice", age: 30 },
{ name: "Bob", age: 25 },
{ name: "Charlie", age: 35 },
])
);
// Result:
// [
// { name: "Bob", age: 25 },
// { name: "Charlie", age: 35 },
// { name: "Alice", age: 30 },
// ];
Sorting a list of integers in descending order:
function sortNumbersDescending(numbers) {
return quickSort(numbers).reverse();
}
console.log(sortNumbersDescending([5, 3, 1, 8, 4, 7, 2, 6]));
// Output: [8, 7, 6, 5, 4, 3, 2, 1]
Sorting a list of dates chronologically:
function sortDates(dates) {
return quickSort(dates, function (a, b) {
return new Date(a) - new Date(b);
});
}
console.log(sortDates(["2022-01-01", "2021-12-31", "2020-01-01"]));
// Output: ["2020-01-01", "2021-12-31", "2022-01-01"]
Sorting a list of products by price:
function sortByPrice(products) {
return quickSort(products, function (a, b) {
return a.price - b.price;
});
}
console.log(
sortByPrice([
{ name: "Product A", price: 50 },
{ name: "Product B", price: 30 },
{ name: "Product C", price: 80 },
]),
);
// Output: [{name: "Product B", price: 30}, {name: "Product A", price: 50}, {name: "Product C", price: 80}]
When to Use Quick Sort
Quick Sort is a highly efficient sorting algorithm with an average time complexity of O(n * log(n)). This means that it performs well even with large datasets, making it a good choice for sorting large arrays or lists.
However, it's worth noting that Quick Sort is not a stable sorting algorithm, which means that it may not preserve the relative order of elements that compare as equal. If stability is important for your use case, you may want to consider using a different sorting algorithm such as Merge Sort.
Overall, Quick Sort is a powerful tool for sorting arrays and lists in JavaScript, and it can be a useful addition to your toolkit as a programmer. Whether you're organizing names, dates, or objects by a specific property, Quick Sort can help you get your data into a more manageable and organized state.
Conclusion
Quick Sort is a fast and efficient sorting algorithm that can be used to organize data in JavaScript. It works by selecting a pivot element and partitioning the rest of the elements into two sub-arrays based on whether they are less than or greater than the pivot. It then repeats this process for each sub-array until all elements are sorted. Quick Sort has an average time complexity of O(n * log(n)) and can be a good choice for sorting large datasets. However, it is not a stable sorting algorithm, so it may not preserve the relative order of elements that compare as equal. Quick Sort can be used in a variety of some scenarios, such as sorting names, dates, or objects by a specific property. Whether you're looking to organize your data or simply want to brush up on your algorithms skills, Quick Sort is a valuable tool to have in your programming toolkit.
Mình hy vọng bạn thích bài viết này và học thêm được điều gì đó mới.
Donate mình một ly cafe hoặc 1 cây bút bi để mình có thêm động lực cho ra nhiều bài viết hay và chất lượng hơn trong tương lai nhé. À mà nếu bạn có bất kỳ câu hỏi nào thì đừng ngại comment hoặc liên hệ mình qua: Zalo - 0374226770 hoặc Facebook. Mình xin cảm ơn.
Momo: NGUYỄN ANH TUẤN - 0374226770
TPBank: NGUYỄN ANH TUẤN - 0374226770 (hoặc 01681423001)
All rights reserved
