Quick

Quick Sort is another popular sorting algorithm that uses the divide-and-conquer paradigm.

It works by selecting a pivot element from the array, partitioning the array into two subarrays based on the pivot element, and then recursively sorting each subarray.

Here are the basic steps of the Quick Sort algorithm:

Data Structures and Algorithms Cheatsheet - Algorithms Section - 9

1. Choose a pivot element from the array.

2. Partition the array into two subarrays: one containing elements smaller than the pivot element, and one containing elements larger than the pivot element.

3. Recursively apply Quick Sort to each subarray until the entire array is sorted.

Quick Sort has a time complexity of O(n log n) on average, making it one of the most efficient sorting algorithms for large datasets.

However, in the worst case (e.g., when the pivot element always selects the maximum or minimum element of the array), Quick Sort can have a time complexity of O(n^2).

This worst-case scenario can be avoided by selecting a good pivot element, such as the median or a random element.

Additionally, Quick Sort is an in-place sorting algorithm, meaning that it does not require additional memory beyond the original array.

pseudocode:

function quickSort(array)
    if length(array) <= 1
        return array
    pivot = choosePivot(array)
    left = []
    right = []
    for each item in array except pivot
        if item <= pivot
            append item to left
        else
            append item to right
    return concatenate(quickSort(left), pivot, quickSort(right))

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function quickSort(array, left, right){
function QuickSort(arr) {
    if (arr.length <= 1) return arr;

    const pivot = arr[Math.floor(Math.random() * arr.length)];

    const left = [];

    const right = [];

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else if (arr[i] > pivot) {
            right.push(arr[i]);
        }
    }

    return [...QuickSort(left), pivot, ...QuickSort(right)];
}

console.log(QuickSort(numbers));

Output

PS D:\Coding Playground> node playground2.js
[
    0,  1,  2,  4,  5, 6, 44, 63, 87, 99, 283
]