Sorting and Searching - Java Concepts - page 881

However, when you write Java programs, you don't have to implement your own
sorting algorithm. The Arrays class contains static sort methods to sort arrays of
integers and floating-point numbers. For example, you can sort an array of integers
simply as

int[] a = . . .;
Arrays.sort(a);

That sort method uses the quicksort algorithmȌsee Advanced Topic 14.3 for more
information about that algorithm.

S ELF C HECK

9. Given the timing data for the merge sort algorithm in the table at the
beginning of this section, how long would it take to sort an array of
100,000 values?

10. Suppose you have an array double [] values in a Java program.
How would you sort it?

A DVANCED T OPIC 14.3: The Quicksort Algorithm

Quicksort is a commonly used algorithm that has the advantage over merge sort
that no temporary arrays are required to sort and merge the partial results.

The quicksort algorithm, like merge sort, is based on the strategy of divide and
conquer. To sort a range a[from ] . . . a[to] of the array a , first
rearrange the elements in the range so that no element in the range a[from] .
. . a[p] is larger than any element in the range a[p + 1] . . . a[to] .
This step is called partitioning the range.

645
646

For example, suppose we start with a range

Here is a partitioning of the range. Note that the partitions aren't yet sorted.