Quicksort

Quick Sort is a popular and efficient sorting algorithm that uses a divide-and-conquer strategy to sort elements in an array or list.

Steps

1. Choose a Pivot: Select an element from the array as the "pivot." There are different strategies for choosing the pivot, such as picking the first element, the last element, a random element, or the median.

2. Partitioning: Rearrange the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it. This is called the partitioning step. The pivot is then in its final position.

3. Recursively Apply: Recursively apply the above steps to the sub-arrays formed by partitioning. The base case for the recursion is when the sub-array has one or zero elements, which are inherently sorted.

Time Complexity

• Average Case: O(nlog⁡n)O(nlogn)
• Worst Case: O(n2)O(n2) (occurs when the smallest or largest element is always chosen as the pivot)
• Best Case: O(nlog⁡n)O(nlogn)

Implementation

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; // Base case: arrays with 0 or 1 element are already sorted
  }

  const pivot = arr[arr.length - 1]; // Choosing the last element as pivot
  const left = []; // Elements less than pivot
  const right = []; // Elements greater than pivot

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

  // Recursively sorting the left and right arrays and concatenating results
  return [...quickSort(left), pivot, ...quickSort(right)];
}

Characteristics

• Quick Sort is generally faster in practice than other O(nlog⁡n)O(nlogn) algorithms like Merge Sort or Heap Sort.
• It is an in-place sort, meaning it requires only a small, constant amount of additional storage space.
• It's not a stable sort, which means that the relative order of equal elements may not be preserved.