DSA Visual

Quick Sort

Step through quick sort's partitioning - see how pivots divide and conquer the array.

About Quick Sort

How Quick Sort Works

Quick sort selects a pivot element and partitions the array so that elements less than the pivot come before it and elements greater come after. It then recursively sorts the partitions. In practice, it is one of the fastest general-purpose sorting algorithms.

Choose a pivot element, then rearrange the array so all elements smaller than the pivot are on its left, and all larger elements are on its right. Recursively apply the same process to the left and right partitions.

Complexity

Time
O(n log n)
Space
O(log n)
Stability
unstable

When to Use Quick Sort

  • General-purpose sorting with excellent average performance
  • In-memory sorting where cache performance matters
  • Large datasets where average-case O(n log n) is acceptable

Approach

Hoare

Implementation

1import random
2
3
4def quick_sort_hoare_random_pivot(arr):
5    if not arr or len(arr) <= 1:
6        return arr
7
8    def separate(low: int, high: int):
9        if low >= high:
10            return
11
12        pivot_pos = random.randint(low, high)
13        pivot = arr[pivot_pos]
14
15        l, r = low - 1, high + 1  # Hoare's method reqires out of bounds initialisation
16
17        while True:
18            while True:
19                l += 1
20                if pivot <= arr[l]:
21                    break
22            while r >= low:
23                r -= 1
24                if pivot >= arr[r]:
25                    break
26            if l >= r:
27                break
28            arr[l], arr[r] = arr[r], arr[l]
29
30        separate(low, r)
31        separate(r + 1, high)
32
33    separate(0, len(arr) - 1)
34    return arr

Quick Sort Animation

Waiting for input...

No steps to display. Please provide input to visualize the algorithm.

-

More in Sorting

Bubble SortO(n²)Insertion SortO(n²)Selection SortO(n²)Merge SortO(n log n)Counting SortO(n + k)