## Prune-and-search / Decrease-and-conqure

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 S

if 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.

Similar Posts:

Your email is never published nor shared.