AI solution for JavaScript Coding Question on BFE.dev
43. implement Quick Sort

Solution:

The basic idea of Quick Sort is to partition the array into two sub-arrays, then recursively sort each sub-array. Here is the implementation in JavaScript:

function quickSort(arr, left, right){
    if (left >= right) return;
    var pivot = arr[left];
    var i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] < pivot) i++;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

// Example usage:
var arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]

The quickSort() function takes an array arr, the left index left, and the right index right as parameters. The initial call should be quickSort(arr, 0, arr.length - 1).

The function first checks if left is greater than or equal to right. If so, the array has 0 or 1 elements and is considered sorted, so the function simply returns.

Otherwise, the function selects the pivot element. In this implementation, we choose the leftmost element in the sub-array.

The function then loops through the remaining elements in the sub-array, swapping elements that are on the wrong side of the pivot. At the end of the loop, the pivot occupies its correct position in the array, with all elements to the left of it less than or equal to it, and all elements to the right of it greater than it.

Finally, the function recursively sorts the left and right sub-arrays.

The time cost for Quick Sort is O(n*log(n)) on average and worst case. However, in the worst case of a pivot selection leading to unbalanced partitions, the time cost can be O(n^2). The algorithm is not stable, meaning that it does not preserve the relative order of equal elements.