🧠

Quicksort

Quicksort animation

  • Divide and conquer
  • Divides a large list into smaller sub-lists
    • Low elements and high elements
  • Recursively sorts the sub-lists
  • Usually done in place with O(log(n))O(log(n)) stack space

Complexity

Average Time Space
O(nlog(n))O(n log(n)) log(n)log(n)

Process

  • Pick an element to be the pivot point
  • Partition
    • Reorder list
    • All elements with value less than pivot come before the pivot
    • All elements with value greater than pivot come after the pivot
    • Pivot is in its final position
  • Recursively apply above steps to sub-list of elements with smaller values and greater values

Implementation

JavaScript

function quickSort(array, lowIndex = 0, highIndex = array.length - 1) {
  // partitionArray operates on the subarray between lowIndex and highIndex (inclusive)
  // Partially sorts subarray into elements less than pivot and elements greater than or equal to pivot
  // Each time it is executed, pivot element is in iits final sorted position
  const partitionArray = (lowIndex, highIndex) => {
    // Swap two elements
    const swap = (leftIndex, rightIndex) => {
      const temp = array[leftIndex];
      array[leftIndex] = array[rightIndex];
      array[rightIndex] = temp;
    }

    // Arbitraily pick last element as a pivot point
    const pivot = array[highIndex];

    let partitionIndex = lowIndex;
    for (let currIndex = lowIndex; currIndex < highIndex; currIndex++) {
      if (array[currIndex] < pivot) {
        swap(partitionIndex, currIndex);
        partitionIndex++;
      }
    }

    // Element at partitionIndex must be greater than or equal to pivot
    // Elements to the left are less than pivot
    // Swapping pivot with partitionIndex places pivot in final sorted position
    swap(partitionIndex, highIndex);

    return partitionIndex;
  }

  if (lowIndex < highIndex) {
    const partitionIndex = partitionArray(lowIndex, highIndex);
    quickSort(array, lowIndex, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, highIndex);
  }

  return array;
}

Computer Science Algorithm

Backlinks