Visualizers

Quick Sort Visualizer

Step-through animation of Quick Sort showing partitioning and pivot choices.

native (Canvas API) Client-side

Input Mode

Array Size (10-50)

Speed

Ready to visualize

Execution Log

Comparisons: 0

Swaps: 0

Current Action:

Idle

Legend:

Unsorted

Pointers (i, j)

Pivot

Sorted / Pivot Placed

Quick Sort Algorithm

Quick Sort is a highly efficient, in-place sorting algorithm. It uses a divide-and-conquer strategy to partition a list into smaller sublists, which are then sorted recursively.

How It Works

Pick an element from the array to serve as the pivot (e.g. the last element).
Reorder the array so that all elements smaller than the pivot come before it, and all elements larger than the pivot come after it. This step is called partitioning.
Recursively apply the above steps to the sub-arrays on the left and right of the pivot.

Implementation

function quickSort(arr, l = 0, r = arr.length - 1) {
  if (l < r) {
    const pIdx = partition(arr, l, r);
    quickSort(arr, l, pIdx - 1);
    quickSort(arr, pIdx + 1, r);
  }
  return arr;
}

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

def quick_sort(arr, l=0, r=None):
    if r is None:
        r = len(arr) - 1
    if l < r:
        p_idx = partition(arr, l, r)
        quick_sort(arr, l, p_idx - 1)
        quick_sort(arr, p_idx + 1, r)
    return arr

def partition(arr, l, r):
    pivot = arr[r]
    i = l - 1
    for j in range(l, r):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    return i + 1

public class QuickSort {
    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            int pIdx = partition(arr, l, r);
            quickSort(arr, l, pIdx - 1);
            quickSort(arr, pIdx + 1, r);
        }
    }

    private static int partition(int[] arr, int l, int r) {
        int pivot = arr[r];
        int i = l - 1;
        for (int j = l; j < r; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[r];
        arr[r] = temp;
        return i + 1;
    }
}

#include <vector>
#include <algorithm>

int partition(std::vector<int>& arr, int l, int r) {
    int pivot = arr[r];
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[r]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int l, int r) {
    if (l < r) {
        int pIdx = partition(arr, l, r);
        quickSort(arr, l, pIdx - 1);
        quickSort(arr, pIdx + 1, r);
    }
}

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.