The quick sort algorithm is a sorting algorithm that sorts an array by partitioning the array into two subarrays, then sorting the subarrays recursively. The algorithm gets its name from the way it sorts the array: it partitions the array into two subarrays, then sorts the subarrays "quickly" by recursively applying the quick sort algorithm.
The quick sort algorithm is usually implemented using recursion. The base case of the recursion is when the array to be sorted has length 1 or 0. In this case, the array is already sorted. Otherwise, the array is partitioned into two subarrays, and the quick sort algorithm is applied recursively to each subarray.
The quick sort algorithm has a time complexity of O(n log n) on average, and a space complexity of O(log n). However, the worst case time complexity of the quick sort algorithm is O(n^2).
The following is a code example of the quick sort algorithm in JavaScript:
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
The following is an exercise to test your understanding of the quick sort algorithm:
// Write a function that sorts an array using the quick sort algorithm.
function quickSort(arr) {
// Your code here
}
The following is the answer code for the exercise:
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
The quick sort algorithm is a very efficient sorting algorithm with a time complexity of O(n log n) on average. However, the worst case time complexity of the quick sort algorithm is O(n^2). Therefore, the quick sort algorithm is not the best sorting algorithm to use in all cases.