♥
±.8. Linear-Time Selection
•
Second, we define a new function
S
(
n
)=
T
(
n
+
α
)
, choosing the constant
α
so that
S
(
n
)
satisfies the simpler recurrence
S
(
n
)
≤
2
S
(
n
/
2
)+
O
(
n
)
. To
find the correct constant
α
, we derive a recurrence for
S
from our given
recurrence for
T
:
S
(
n
)=
T
(
n
+
α
)
[definition of
S
]
≤
2
T
(
n
/
2
+
α/
2
+
1
)+
n
+
α
[recurrence for
T
]
=
2
S
(
n
/
2
-
α/
2
+
1
)+
n
+
α
[definition of
S
]
Setting
α
=
2
simplifies this recurrence to
S
(
n
)
≤
2
S
(
n
/
2
)+
n
+
2
, which is
exactly what we wanted.
•
Finally, the recursion tree method implies
S
(
n
)=
O
(
n
log
n
)
, and therefore
T
(
n
)=
S
(
n
-
2
)=
O
((
n
-
2
)
log
(
n
-
2
)) =
O
(
n
log
n
)
,
exactly as promised.
Similar domain transformations can be used to remove floors, ceilings, and even
lower order terms from
any
divide and conquer recurrence. But now that we
realize this, we don’t need to bother grinding through the details ever again!
From now on, faced with any divide-and-conquer recurrence, I will silently
brush floors and ceilings and lower-order terms under the rug, and I encourage
you to do the same.
♥
².8
Linear-Time Selection
During our discussion of quicksort, I claimed in passing that we can find the
median of an unsorted array in linear time.
The first such algorithm was
discovered by Manuel Blum, Bob Floyd, Vaughan Pratt, Ron Rivest, and Bob
Tarjan in the early ´¶º±s. Their algorithm actually solves the more general
problem of selecting the
k
th smallest element in an
n
-element array, given the
array and the integer
k
as input, using a variant of an algorithm called
quickselect
or
one-armed quicksort
.
Quickselect was first described by Tony Hoare in ´¶¹´,
literally on the same page where he first published quicksort.
Quickselect
The generic quickselect algorithm chooses a pivot element, partitions the array
using the same
P±µ²´²´¸¾
subroutine as
Q·´¶ÈS¸µ²
, and then recursively
searches
only one
of the two subarrays, specifically, the one that contains the
k
th smallest element of the original input array. Pseudocode for quickselect is
given in Figure ´.´³.
²³