Quick Sort

Quick Sort is an efficient sorting algorithm that uses a divide-and-conquer approach. It works by selecting a value (called a pivot) and partitioning the array into elements that are smaller and larger than the pivot.

It is widely used because of its strong average performance and simplicity. However, its performance can degrade in certain cases depending on how the pivot is chosen.

How It Works

Quick Sort works by partitioning the array:

Choose a pivot element from the array.
Rearrange the array so that:
- Values smaller than the pivot come before it.
- Values larger than the pivot come after it.
The pivot is now in its correct position.
Recursively apply the same process to the left and right partitions.
Repeat until all elements are sorted.

This process breaks the problem into smaller subproblems, which are solved independently.

JavaScript Example


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)
  ];
}

// Example usage
const values = [29, 10, 14, 37, 13];

console.log(quickSort(values)); // [10, 13, 14, 29, 37]