# Linear-time Partitioning

The real work of quicksort happens during the divide step, which partitions subarray

Having chosen a pivot, we partition the subarray by going through it, left to right, comparing each element with the pivot. We maintain two indices `q`

and `j`

into the subarray that divide it up into four groups. We use the variable name `q`

because that index will eventually point at our pivot. We use `j`

because it's a common counter variable name, and the variable will be discarded once we're done.

The elements in

$array[p \cdots q-1]$ are "group L," consisting of elements known to be less than or equal to the pivot.The elements in

$array[q \cdots j-1]$ are "group G," consisting of elements known to be greater than the pivot.The elements in

$array[j \cdots r-1]$ are "group U," consisting of elements whose relationship to the pivot is unknown, because they have not yet been compared.Finally,

$array[r]$ is "group P," the pivot.

Initially, both `q`

and `j`

equal `p`

. At each step, we compare `j`

, so that the line dividing groups G and U slides over one position to the right:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy