loading
loading
loading
Computer Science / Algorithms
Partition around a pivot so smaller elements land left and larger land right, then recurse — fast in practice, O(n²) on an unlucky pivot.
Quick sort picks a pivot, then partitions the array so every value smaller than the pivot ends up to its left and every value larger ends up to its right — after which the pivot sits in its final sorted position, guaranteed. It then recurses on the two sub-ranges on either side. This visualizer always picks the last element of the current range as the pivot (the Lomuto partition scheme) for pedagogical clarity — a simple, deterministic rule to follow by eye, not the fastest one in practice. That choice matters: on an already-sorted or reverse-sorted array, last-element pivoting produces the most unbalanced possible partition at every step, degrading to O(n²). Randomized or median-of-three pivot selection avoids this in practice but isn't implemented here. Press Shuffle to generate a new random array and watch the partitioning process repeat.
Last-element pivoting (the Lomuto partition scheme) is the simplest deterministic rule to follow by eye, which makes it the clearest teaching choice — but it isn't the fastest one in practice. Randomized pivoting or median-of-three selection avoid its worst case, but neither is implemented here.
If the chosen pivot is always the smallest or largest remaining value — which happens on every step when the input is already sorted (or reverse-sorted), since the pivot is always the last element — every partition splits the range into one empty side and one side of size n−1. The algorithm then degrades to n nested passes instead of log n halvings.
No. The partition step swaps elements based on comparison to the pivot alone, without tracking original order, so two elements with equal keys can end up reordered relative to each other.