Quick Sort Visualization

Quick Sort

Algorithm Explanation

Quick Sort is a highly efficient divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. This process continues until the base case of an empty or single-item array is reached.

Time Complexity:

Best Case: O(n log n) - when the pivot always divides the array in the middle
Average Case: O(n log n)
Worst Case: O(n²) - when the smallest or largest element is always chosen as pivot

Space Complexity: O(log n) - due to the recursive call stack

Key Features:

In-place sorting (requires small additional space)
Unstable sort (relative order of equal elements may change)
Typically faster than merge sort for arrays that fit in memory

Visualization Guide

This visualization shows the step-by-step process of Quick Sort:

Each row represents a stage in the sorting process
The black box highlights the current subarray being sorted
Pivot elements are shown in purple
Sorted elements are shown in green
Unsorted elements are shown in red
The median-of-three strategy is used to select pivots for better average performance

Note: This visualization style is based on the classic approach used in CS education courses to demonstrate the recursive nature of Quick Sort.

Custom Input

Enter numbers separated by commas. Example: 5, 3, 8, 1, 2

Array Size:

Speed:

Code Implementation

function quickSort(arr) {
  // Base case: arrays with 0 or 1 element are already sorted
  if (arr.length <= 1) {
    return arr;
  }
  
  // Choose a pivot (here we choose the last element)
  const pivot = arr[arr.length - 1];
  
  // Create arrays for elements less than and greater than the pivot
  const less = [];
  const greater = [];
  
  // Partition the array
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      less.push(arr[i]);
    } else {
      greater.push(arr[i]);
    }
  }
  
  // Recursively sort the sub-arrays and combine with pivot
  return [...quickSort(less), pivot, ...quickSort(greater)];
}