AlgoViz: Interactive Algorithm Visualization Tool

Quick Sort

Category: Sorting | Time: O(n log n) | Space: O(log n)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Quick Sort

An efficient, in-place, comparison-based sorting algorithm. It applies the divide-and-conquer strategy. 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 sorted recursively.

Code Editor

The code is for reference. Editing it won't affect the visualization.

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

function partition(arr, low, high) {
  let pivot = arr[high];
  let i = (low - 1);
  for (let j = low; j <= high - 1; 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);
}

What is Quick Sort?

What is the time complexity of Quick Sort?

Is Quick Sort an in-place algorithm?

Is Quick Sort stable?

How does the choice of pivot affect performance?

What are common pivot selection strategies?

What is the Lomuto partition scheme?

When would you not use Quick Sort?

What is a dual-pivot Quick Sort?

Can Quick Sort be implemented iteratively?

Where can I learn more?