Quick sort – JavaScript

Quick sort is a popular sorting algorithm that has an average case time complexity of O(n log n) and is often used as a faster alternative to other sorting algorithms such as bubble sort or insertion sort. It 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. The sub-arrays are then recursively sorted using the same process.

Here is an example of how to implement quick sort in JavaScript:

Copy Code


function quickSort(arr) {
    if (arr.length <= 1) {
    return arr;
}

const pivot = arr[0];
const left = [];
const right = [];

for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
        left.push(arr[i]);
    } else {
        right.push(arr[i]);
    }
}
    return [...quickSort(left), pivot, ...quickSort(right)];
}

const sortedArray = quickSort([5, 3, 8, 1, 2, 9, 4]);
console.log(sortedArray); // [1, 2, 3, 4, 5, 8, 9]

In the example above, we first check if the input array has a length of 1 or less. If it does, we simply return the array as it is already sorted. If the array has more than one element, we select the first element as the pivot and create two empty arrays called left and right.

We then iterate over the rest of the elements in the array and compare them to the pivot. If the element is less than the pivot, it is added to the left array. If it is greater than or equal to the pivot, it is added to the right array.

Finally, we return a new array that is the result of recursively sorting the left array, followed by the pivot element, followed by the result of recursively sorting the right array.

Using this approach, we can quickly and efficiently sort an array of values in ascending order.

Categories: Algorithms