Sorting algorithms - Data Structures and Problem Solving Using Java - page 380

adjust them before the array accesses at lines 37 and 39. When the first while
loop at line 37 exits, i will be indexing an element that is greater than or pos-
sibly equal to the pivot. Likewise, when the second loop ends, j will be index-
ing an element that is less than or possibly equal to the pivot. If i and j have
not crossed, these elements are swapped and we continue scanning. Other-
wise, the scan is terminated and the pivot is restored at line 46. The sort is fin-
ished when the two recursive calls are made at lines 48 and 49.

The fundamental operations occur at lines 37 through 40. The scans con-
sist of simple operations: increments, array accesses, and simple comparisons,
accounting for the “quick” in quicksort. To ensure that the inner loops are
tight and efficient, we want to be sure that the swap at line 43 comprises the
three assignments that we expect and does not incur the overhead of a method
call. Thus we declare that the swapReferences routine is a final static method,
or in some cases, we write the three assignments explicitly (e.g., if the com-
piler exercises its right to not perform inline optimization).

The inner loop of
quicksort is very
tight and efficient.

Although the code looks straightforward now, that is only because of the
analysis we performed prior to coding. Additionally, some traps are still lurk-
ing (see Exercise 8.16). Quicksort is a classic example of using an analysis to
guide a program implementation.

Quicksort is a clas-
sic example of
using an analysis to
guide program
implementation.

quickselect

8.7

A problem closely related to sorting is selection, or finding the k th smallest
element in an array of N items. An important special case is finding the
median, or the N / 2th smallest element. Obviously, we can sort the items,
but as selection requests less information than sorting, we hope that selec-
tion would be a faster process. That turns out to be true. By making a small
change to quicksort, we can solve the selection problem in linear time on
average, giving us the algorithm quickselect. The steps for Quickselect ( S, k )
are as follows.

Selection is finding
the k th smallest
element of an array.

1. If the number of elements in S is 1, presumably k is also 1, so we can

return the single element in S .

2. Pick any element v in S . It is the pivot.

3. Partition S - { v } into L and R, exactly as was done for quicksort.

4. If k is less than or equal to the number of elements in L, the item we

are searching for must be in L . Call Quickselect( L, k ) recursively.
Otherwise, if k is exactly equal to 1 more than the number of items
in L, the pivot is the k th smallest element, and we can return it as the