Nonlinear General Selection Algorithm
Using the same ideas used in minimum/maximum algorithms, we can construct a simple, but inefficient general algorithm for finding the kth smallest or kth largest item in a list, requiring O(kn) time, which is effective when k is small. To accomplish this, we simply find the most extreme value and move it to the beginning until we reach our desired index. This can be seen as an incomplete selection sort. Here is the minimum-based algorithm:
function select(list, k) for i from 1 to k minIndex = i minValue = list for j from i+1 to n if list < minValue minIndex = j minValue = list swap list and list return listOther advantages of this method are:
- After locating the jth smallest element, it requires only O(j + (k-j)2) time to find the kth smallest element, or only O(1) for k ≤ j.
- It can be done with linked list data structures, whereas the one based on partition requires random access.
Read more about this topic: Selection Algorithm
Famous quotes containing the words general and/or selection:
“We ought, says Kant, to become acquainted with the instrument, before we undertake the work for which it is to be employed; for if the instrument be insufficient, all our trouble will be spent in vain. The plausibility of this suggestion has won for it general assent and admiration.... But the examination can be only carried out by an act of knowledge. To examine this so-called instrument is the same as to know it.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“When you consider the radiance, that it does not withhold
itself but pours its abundance without selection into every
nook and cranny”
—Archie Randolph Ammons (b. 1926)