Java Reference
In-Depth Information
Extending the Partitions
646
647
Then keep incrementing i while a[i] < pivot and keep decrementing j while
a[j] > pivot . Extending the Partitions shows i and j when that process stops.
Now swap the values in positions i and j , increasing both areas once more. Keep
going while i < j . Here is the code for the partition method:
private int partition (int from, int to)
{
int pivot = a[from];
int i = from - 1;
int j = to + 1;
while (i < j)
{
i++; while (a[i] < pivot) i++;
j--; while (a[j] > pivot) j--;
if (i < j) swap(i, j);
}
return j;
}
On average, the quicksort algorithm is an O(n log(n)) algorithm. Because it is
simpler, it runs faster than merge sort in most cases. There is just one unfortunate
aspect to the quicksort algorithm. Its worst-case runtime behavior is O(n 2 ).
Moreover, if the pivot element is chosen as the first element of the region, that
worst-case behavior occurs when the input set is already sortedȌa common
situation in practice. By selecting the pivot element more cleverly, we can make it
extremely unlikely for the worst-case behavior to occur. Such Ȓtunedȓ quicksort
algorithms are commonly used, because their performance is generally excellent.
For example, as was mentioned, the sort method in the Arrays class uses a
quicksort algorithm.
Search WWH ::




Custom Search