prep4place
Back to Visualizer

Quick Sort

Quick Sort is a highly efficient divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around it. It's widely used due to its excellent average-case performance.

Best: O(n log n)Avg: O(n log n)Space: O(log n)
Size:20
Speed:50%
Default
Comparing
Swapping
Sorted
Pivot
Current
0
Comparisons
0
Swaps

How It Works

  1. 1Choose a pivot element (typically last element)
  2. 2Partition: place smaller elements before pivot, larger after
  3. 3The pivot is now in its final sorted position
  4. 4Recursively apply to left sub-array
  5. 5Recursively apply to right sub-array
  6. 6Continue until all elements are in place

Time Complexity

Best CaseO(n log n)
Average CaseO(n log n)
Worst CaseO(n²)
Space ComplexityO(log n)

Code

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}