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 all have known
Good critics, who have stamped out poet’s hopes;
Good statesmen, who pulled ruin on the state;
Good patriots, who, for a theory, risked a cause;
Good kings, who disembowelled for a tax;
Good Popes, who brought all good to jeopardy;
Good Christians, who sat still in easy-chairs;
And damned the general world for standing up.—
Now, may the good God pardon all good men!”
—Elizabeth Barrett Browning (1806–1861)
“Judge Ginsburg’s selection should be a model—chosen on merit and not ideology, despite some naysaying, with little advance publicity. Her treatment could begin to overturn a terrible precedent: that is, that the most terrifying sentence among the accomplished in America has become, “Honey—the White House is on the phone.””
—Anna Quindlen (b. 1952)