Java Reference
In-Depth Information
You'll see later how to obtain such a partition. In the next step, sort each partition,
by recursively applying the same algorithm on the two partitions. That sorts the
entire range, because the largest element in the first partition is at most as large as
the smallest element in the second partition.
Quicksort is implemented recursively as follows:
public void sort(int from, int to)
{
if (from >= to) return;
int p = partition(from, to);
sort(from, p);
sort(p + 1, to);
}
Let us return to the problem of partitioning a range. Pick an element from the
range and call it the pivot. There are several variations of the quicksort algorithm.
In the simplest one, we'll pick the first element of the range,
a[from]
, as the
pivot.
Now form two regions
a[from] . . . a[i]
, consisting of values at most as
large as the pivot and
a[j] . . . a[to]
, consisting of values at least as large
as the pivot. The region
a[i + 1] . . . a[j - 1]
consists of values that
haven't been analyzed yet. (See Partitioning a Range.) At the beginning, both the
left and right areas are empty; that is,
i = from - 1
and
j = to + 1
.
Partitioning a Range
