Once given n elements, the Prune-and-search (=Decrease and Conquer) removes a fraction of elements recursively, until the number of elements reaches a predefined threshold. If the threshold is hit, the algorithm performs brute-force searching.
Following is an example of finding the kth smallest value from n elements which demonstrates the idea of prune-and-search.
Algorithm quickSelect(S, k):
Input: Sequence S of n comparable elements, and an integer k which is between 1 and n
Output: The kth smallest elements of Sif n = 1 then
return the (first) element of S
pick a random element x of S
remove all the elements from S and put them into three sequences
– L, storing the elements in S less than x
– E, storing the elements in S equal to x
– G, storing the elements in S greater than x.if k <= |L| then
quickSelect(L, x)
else if k <= |L| + |E| then
return x
else
quickSelect(G, k – |L| – |E|)
The time complexity of the algorithm quickSelect is O(n2) in worst case and runs in O(n) expected time.
Leave a Reply