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:
“A writer who writes, “I am alone” ... can be considered rather comical. It is comical for a man to recognize his solitude by addressing a reader and by using methods that prevent the individual from being alone. The word alone is just as general as the word bread. To pronounce it is to summon to oneself the presence of everything the word excludes.”
—Maurice Blanchot (b. 1907)
“Every writer is necessarily a critic—that is, each sentence is a skeleton accompanied by enormous activity of rejection; and each selection is governed by general principles concerning truth, force, beauty, and so on.... The critic that is in every fabulist is like the iceberg—nine-tenths of him is under water.”
—Thornton Wilder (1897–1975)