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

answer. Otherwise, the k th smallest element lies in R, and it is the
( k - | L | - 1)th smallest element in R . Again, we can make a recur-
sive call and return the result.

Quickselect makes only one recursive call compared to quicksort's two.
The worst case of quickselect is identical to that of quicksort and is qua-
dratic. It occurs when one of the recursive calls is on an empty set. In such
cases quickselect does not save much. We can show that the average time is
linear, however, by using an analysis similar to that used for quicksort (see
Exercise 8.9).
The implementation of quickselect, shown in Figure 8.23, is simpler than
our abstract description implies. Except for the extra parameter, k, and the
recursive calls, the algorithm is identical to quicksort. When it terminates, the
k th smallest element is in its correct position in the array. As the array begins
at index 0, the fourth smallest element is in position 3. Note that the original
ordering is destroyed. If this situation is undesirable, we can have the driver
routine pass a copy of the array instead.

Quickselect is used
to perform a selec-
tion. It is similar to
quicksort but
makes only one
recursive call. The
average running
time is linear.

Using median-of-three partitioning makes the chance of the worst case
occurring almost negligible. By carefully choosing the pivot, we can ensure
that the worst case never occurs and that the running time is linear even in
the worst-case scenario. The resulting algorithm is entirely of theoretical
interest, however, because the constant that the Big-Oh notation hides is
much larger than the constant obtained in the normal median-of-three
implementation.

The linear worst-
case algorithm is a
classic result even
though it is imprac-
tical.

a lower bound for sorting

8.8

Although we have O ( N log N ) algorithms for sorting, it is not clear that this is
as good as we can do. In this section we prove that any algorithm for sorting
that uses only comparisons requires Ω ( N log N ) comparisons (and hence
time) in the worst case. In other words, any algorithm that sorts by using ele-
ment comparisons must use at least roughly N log N comparisons for some
input sequence. We can use a similar technique to show that this condition
holds on average.

Any comparison-
based sorting algo-
rithm must use
roughly N log N
comparisons on
average and in the
worst case.

Must every sorting algorithm work by using comparisons? The answer is
no. However, algorithms that do not involve the use of general comparisons
are likely to work only for restricted types, such as integers. Although we may
often need to sort only integers (see Exercise 8.17), we cannot make such
sweeping assumptions about the input of a general-purpose sorting algorithm.

The proofs are
abstract; we show
the worst-case
lower bound.