SimuVedaAlgorithms Lab Open in the lab

Sorting / Intermediate

Quick Sort Visualizer

Pick a pivot, move smaller values to its left and bigger ones to its right, then sort each side the same way.

Start the Quick Sort simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n log n)
Average timeO(n log n)
Worst timeO(n²)
Extra spaceO(log n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Quick sort on 5 values, using the last value as the pivot. [5, 1, 4, 2, 8]
  2. Partition [0..4] around the pivot 8.
  3. Is 5 smaller than the pivot 8?
  4. Yes. It is already on the left side.
  5. Is 1 smaller than the pivot 8?
  6. Yes. It is already on the left side.
  7. Is 4 smaller than the pivot 8?
  8. Yes. It is already on the left side.
  9. Is 2 smaller than the pivot 8?
  10. Yes. It is already on the left side.
  11. Put the pivot 8 at index 4. Everything left is smaller, everything right is bigger.
  12. Partition [0..3] around the pivot 2.
  13. Is 5 smaller than the pivot 2?
  14. Is 1 smaller than the pivot 2?
  15. Yes. Swap it to the left side, index 0. [1, 5, 4, 2, 8]
  16. Is 4 smaller than the pivot 2?
  17. Put the pivot 2 at index 1. Everything left is smaller, everything right is bigger. [1, 2, 4, 5, 8]
  18. [0..0] has one value. It is in place.
  19. Partition [2..3] around the pivot 5.
  20. Is 4 smaller than the pivot 5?
  21. Yes. It is already on the left side.
  22. Put the pivot 5 at index 3. Everything left is smaller, everything right is bigger.
  23. [2..2] has one value. It is in place.
  24. Sorted. 8 comparisons and 2 swaps.

Try it with your own input →

Quick sort in Java, Python, C++, C and JavaScript

void quickSort(int[] a, int lo, int hi) {
  if (lo >= hi) return;
  int p = partition(a, lo, hi);
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
}
int partition(int[] a, int lo, int hi) {
  int pivot = a[hi];
  int i = lo;
  for (int j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      swap(a, i, j);
      i++;
    }
  }
  swap(a, i, hi);
  return i;
}
def quick_sort(a, lo, hi):
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    quick_sort(a, lo, p - 1)
    quick_sort(a, p + 1, hi)

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i
int partition(vector<int>& a, int lo, int hi);

void quickSort(vector<int>& a, int lo, int hi) {
  if (lo >= hi) return;
  int p = partition(a, lo, hi);
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
}
int partition(vector<int>& a, int lo, int hi) {
  int pivot = a[hi];
  int i = lo;
  for (int j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      swap(a[i], a[j]);
      i++;
    }
  }
  swap(a[i], a[hi]);
  return i;
}
int partition(int a[], int lo, int hi);

void quickSort(int a[], int lo, int hi) {
  if (lo >= hi) return;
  int p = partition(a, lo, hi);
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
}
int partition(int a[], int lo, int hi) {
  int pivot = a[hi], t;
  int i = lo;
  for (int j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      t = a[i]; a[i] = a[j]; a[j] = t;
      i++;
    }
  }
  t = a[i]; a[i] = a[hi]; a[hi] = t;
  return i;
}
function quickSort(a, lo, hi) {
  if (lo >= hi) return;
  const p = partition(a, lo, hi);
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
}
function partition(a, lo, hi) {
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }
  [a[i], a[hi]] = [a[hi], a[i]];
  return i;
}

In an interview

Try the Reversed preset: always picking the last value as the pivot hits the O(n²) worst case. A random pivot avoids it.

More sorting