View source for Selection algorithm

In [[computer science]], a '''selection algorithm''' is an [[algorithm]] for finding the ''k''th smallest number in a list, called ''[[order statistic]]s''. This includes the cases of finding the minimum, maximum, and median elements. There are worst-case linear time selection algorithms. Selection is a subproblem of more complex problems like the [[nearest neighbor problem]] and [[shortest path]] problems.

The term "selection" is used in other contexts in computer science, including the stage of a genetic algorithm in which genomes are chosen from a population for later breeding; see [[Selection (genetic algorithm)]].  This article addresses only the problem of determining order statistics.

== Selection by sorting ==
Selection can be [[Reduction (complexity)|reduced]] to [[sorting algorithm|sorting]] by sorting the list and then extracting the desired element.  This method is efficient when many selections need to be made from a list, in which case only one initial, expensive sort is needed, followed by many cheap extraction operations. In general, this method requires O;(''n''&nbsp;log ''n'') time, where ''n'' is the length of the list.

==Linear minimum/maximum algorithms==
Linear time algorithms to find minimums or maximums work by iterating over the list and keeping track of the minimum or maximum element so far.

== 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 ''k''th smallest or ''k''th 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[1..n], k)
      '''for''' i '''from''' 1 '''to''' k
          minIndex = i
          minValue = list[i]
          '''for''' j '''from''' i+1 '''to''' n
              '''if''' list[j] < minValue
                  minIndex = j
                  minValue = list[j]
          swap list[i] and list[minIndex]
      '''return''' list[k]

Other advantages of this method are:
* After locating the ''j''th smallest element, it requires only O(''j'' + (''k''-''j'')<sup>2</sup>) time to find the ''k''th smallest element, or only O(''k'') for ''k'' ≤ ''j''.
* It can be done with [[linked list]] data structures, whereas the one based on partition requires [[random access]].

== Partition-based general selection algorithm ==

A worst-case linear algorithm for the general case of selecting the ''k''th largest element was published by Blum, Floyd, Pratt, Rivest, and Tarjan in their 1973 paper ''Time bounds for selection''. The algorithm that it is based on was conceived by the inventor of [[quicksort]], [[C.A.R. Hoare]], and are known as '''Hoare's selection algorithm'''.

In quicksort, there is a subprocedure called partition which can, in linear time, group the list into two parts, those less than a certain value (<code>left</code>), and those greater than or equal to a certain value (<code>right</code>, which ends up containing <code>pivotValue</code>). Here is pseudocode which performs a partition about the value <code>list[pivotIndex]</code>:

  '''function''' partition(list, left, right, pivotIndex)
      pivotValue := list[pivotIndex]
      swap list[pivotIndex] and list[right]  ''// Move pivot to end''
      storeIndex := left
      '''for''' i '''from''' left '''to''' right-1
          '''if''' list[i] < pivotValue
              swap list[storeIndex] and list[i]
              storeIndex := storeIndex + 1
      swap list[right] and list[storeIndex]  ''// Move pivot to its final place''
      '''return''' storeIndex

In quicksort, we recursively sort both branches, leading to best-case [[Big-O notation|Ω]](''n'' log ''n'') time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in sorted order preceding it and all those following it in sorted order following it. Thus a single recursive call locates the desired element in the correct partition:

  '''function''' select(list, k, left, right)
      select a pivot value list[pivotIndex]
      pivotNewIndex := partition(list, left, right, pivotIndex)
      '''if''' k = pivotNewIndex
          '''return''' list[k]
      '''else if''' k < pivotNewIndex
          '''return''' select(list, k, left, pivotNewIndex-1)
      '''else'''
          '''return''' select(list, k-pivotNewIndex, pivotNewIndex+1, right)

Note the resemblance to quicksort; indeed, just as the minimum-based selection algorithm is a partial selection sort, this is a partial quicksort, generating and partitioning only O(log ''n'') of its O(''n'') partitions. This simple procedure has expected linear performance, and, like quicksort, has quite good performance in practice. It is also an [[in-place algorithm]], requiring only constant memory overhead, since the [[tail recursion]] can be eliminated with a loop like this:

  '''function''' select(list, k, left, right)
      '''loop'''
          select a pivot value list[pivotIndex]
          pivotNewIndex := partition(list, left, right, pivotIndex)
          '''if''' k = pivotNewIndex
              return list[k]
          '''else if''' k < pivotNewIndex
              right := pivotNewIndex-1
          '''else'''
              left := pivotNewIndex+1
 
Like quicksort, the performance of the algorithm is sensitive to the pivot that is chosen. If bad pivots are consistently chosen, this degrades to the minimum-based selection described previously, and so can require as much as &Omega;(''n''<sup>2</sup>) time. David Musser describes a "median-of-3 killer" sequence that can force the well-known median-of-three pivot selection algorithm to fail with worst-case behavior (see ''[[#Introselect|Introselect]]'' section below).

== Linear general selection algorithm - "Median of Medians algorithm" ==

The key to making the previous algorithm worst-case linear and the primary contribution of "Time bounds for selection" is the "median of medians algorithm", which consistently finds good pivots.

This algorithm divides the list into groups of five elements. Left over elements are ignored for now. Then, for each group of five, the median is calculated: an operation that can potentially be made very fast if the five values can be loaded into registers and compared. These medians are moved into one contiguous block in the list, ''select'' is called recursively on this sublist of ''n''/5 elements to find new median values. Finally, the "median of medians" is the pivot.

The chosen pivot is both less than and greater than half of the elements in the list of medians, which consists of ''n''/10 elements. Each of these elements is a median of 5, making them both less than and greater than 2 others outside the block, or 2(''n''/10) elements. Thus the chosen median splits the elements somewhere between 30%/70% and 70%/30%, which assures worst-case linear behavior of the algorithm.

The median-calculating recursive call does not exceed worst-case linear behavior because the list of medians is 20% of the size of the list, while the other recursive call recurs on at most 70% of the list, making the running time

  T(''n'') ≤ T(''n''/5) + T(7''n''/10) + O(''n'')

The O(''n'') is for the partitioning work. An induction argument can then show that T(''n'') is indeed O(''n'').

Although this approach optimizes quite well, it is typically outperformed in practice by the expected linear algorithm with random pivot choices.

The worst-case algorithm can construct a worst-case O( n*log(n) ) quicksort algorithm, by using it to find the median at every step.

== Introselect ==

David Musser's well-known [[introsort]] achieves practical performance comparable to quicksort while preserving O(''n'' log ''n'') worst-case behavior by creating a hybrid of quicksort and [[heapsort]]. In the same paper, Musser introduced an "introspective selection" algorithm, popularly called '''introselect''', which combines Hoare's algorithm with the worst-case linear algorithm described above to achieve worst-case linear selection with performance similar to Hoare's algorithm.<ref>David R. Musser. Introspective Sorting and Selection Algorithms. ''Software: Practice and Experience'', vol. 27, no. 8, pp.983&ndash;993. 1997. Section: Introspective Selection Algorithms.</ref> It works by optimistically starting out with Hoare's algorithm and only switching to the worst-time linear algorithm if it recurs too many times without making sufficient progress. Simply limiting the recursion to constant depth is not good enough, since this would make the algorithm switch on all sufficiently large lists. Musser discusses a couple simple approaches:
* Keep track of the list of sizes of the subpartitions processed so far. If at any point ''k'' recursive calls have been made without halving the list size, for some small positive ''k'', switch to the worst-case linear algorithm.
* Sum the size of all partitions generated so far. If this exceeds the list size times some small positive constant ''k'', switch to the worst-case linear algorithm. This sum is easy to track in a single scalar variable.

Both approaches limit the recursion depth to O(''k''log ''n''), which is O(log ''n'') since ''k'' is a predetermined constant. The paper suggested that more research on introselect was forthcoming, but as of 2007 it has not appeared.

== Selection as incremental sorting ==
One of the advantages of the sort-and-index approach, as mentioned, is its ability to [[amortized analysis|amortize]] the sorting cost over many subsequent selections. However, sometimes the number of selections that will be done is not known in advance, and may be either small or large. In these cases, we can adapt the algorithms given above to simultaneously select an element while partially sorting the list, thus accelerating future selections. 

Both the selection procedure based on minimum-finding and the one based on partitioning can be seen as a form of partial sort. The minimum-based algorithm sorts the list up to the given index, and so clearly speeds up future selections, especially of smaller indexes. The partition-based algorithm does not achieve the same behaviour automatically, but can be adapted to remember its previous pivot choices and reuse them wherever possible, avoiding costly partition operations, particularly the top-level one. The list becomes gradually more sorted as more partition operations are done incrementally; no pivots are ever "lost." If desired, this same pivot list could be passed on to quicksort to reuse, again avoiding many costly partition operations.

== Using data structures to select in sublinear time ==
Given an unorganized list of data, linear time (Ω(''n'')) is required to find the minimum element, because we have to examine every element (otherwise, we might miss it). If we organize the list, for example by keeping it sorted at all times, then selecting the ''k''th largest element is trivial, but then insertion requires linear time, as do other operations such as combining two lists.

The strategy to find an order statistic in [[sublinear time]] is to store the data in an organized fashion using suitable data structures that facilitate the selection. Two such data structures are tree based structures and frequency tables.

When only the minimum (or maximum) is needed, a good approach is to use a [[priority queue]], which is able to find the minimum (or maximum) element in constant time, while all other operations, including insertion, are O(log ''n'') or better. More generally, a [[self-balancing binary search tree]] can easily be augmented to make it possible to both insert an element and find the ''k''th largest element in O(log ''n'') time. We simply store in each node a count of how many descendants it has, and use this to determine which path to follow. The information can be updated efficiently since adding a node only affects the counts of its O(log ''n'') ancestors, and tree rotations only affect the counts of the nodes involved in the rotation.

Another simple strategy is based on some of the same concepts as the [[hash table]]. When we know the range of values beforehand, we can divide that range into ''h'' subintervals and assign these to ''h'' buckets. When we insert an element, we add it to the bucket corresponding to the interval it falls in. To find the minimum or maximum element, we scan from the beginning or end for the first nonempty bucket and find the minimum or maximum element in that bucket. In general, to find the ''k''th element, we maintain a count of the number elements in each bucket, then scan the buckets from left to right adding up counts until we find the bucket containing the desired element, then use the expected linear-time algorithm to find the correct element in that bucket.

If we choose ''h'' of size roughly sqrt(''n''), and the input is close to uniformly distributed, this scheme can perform selections in expected O(sqrt(''n'')) time. Unfortunately, this strategy is also sensitive to clustering of elements in a narrow interval, which may result in buckets with large numbers of elements (clustering can be eliminated through a good hash function, but finding the element with the ''k''th largest hash value isn't very useful). Additionally, like hash tables this structure requires table resizings to maintain efficiency as elements are added and ''n'' becomes much larger than ''h''<sup>2</sup>. A useful case of this is finding an order statistic or extremum in a finite range of data,  like marks limited 1 to 100 numbers for much higher number of students. Using above table with bucket interval 1 and maintaining counts in each bucket is much superior to other methods. Such hash tables are like [[frequency tables]] used to classify the data in [[descriptive statistics]].

== Selecting k smallest or largest elements ==
Another fundamental selection problem is that of selecting the ''k'' smallest or ''k'' largest elements, which is particularly useful where we want to present just the "top ''k''" of a sorted list, such as the top 100 corporations by gross sales. 

=== Repeated application of simple selection algorithms ===

A number of simple but inefficient solutions are possible. We can use the linear-time solutions discussed above to select each element one at a time, resulting in time O(''kn'') &mdash; we can achieve the same time just by running the first ''k'' iterations of [[selection sort]]. If log ''n'' is much less than ''k'', a better simple strategy is to sort the list and then take the first or last ''k'' elements.

=== Data structure based solutions ===

Another simple method is to add each element of the list into an ordered set data structure, such as a [[heap (data structure)|heap]] or [[self-balancing binary search tree]], with at most ''k'' elements. Whenever the data structure has more than ''k'' elements, we remove the largest element, which can be done in O(log ''k'') time. Each insertion operation also takes O(log ''k'') time, resulting in O(''n''log ''k'') time overall.


It is possible to transform the list into a [[heap (data structure)|heap]] at Θ(''n'') time, and then scan the heap using a modified [[Breadth-first search]] algorithm that places the elements in a [[Priority Queue]] (instead of the ordinary queue that is normally used in a BFS), and terminate the scan after traversing exactly k elements. As the queue size remains O(''k'') throughout the scan, it would require O(''k''log ''k'') time to complete, leading to a O(''n'' + ''k''log ''k'') time bound on this algorithm.

=== Optimised sorting algorithms ===
More efficient than any of these are specialized partial sorting algorithms based on [[mergesort]] and [[quicksort]]. The simplest is the quicksort variation: there is no need to recursively sort partitions which only contain elements that would fall after the ''k''th place in the end. Thus, if the pivot falls in position ''k'' or later, we only recur on the left partition:

  '''function''' quicksortFirstK(list, left, right, k)
      '''if''' right > left
          select a pivot value list[pivotIndex]
          pivotNewIndex := partition(list, left, right, pivotIndex)
          quicksortFirstK(list, left, pivotNewIndex-1, k)
          '''if''' pivotNewIndex < k
              quicksortFirstK(list, pivotNewIndex+1, right, k)

The resulting algorithm requires an expected time of only O(''n'' + ''k''log''k''), and is quite efficient in practice, especially if we substitute selection sort when ''k'' becomes small relative to ''n''.

Even better is if we don't require those ''k'' items to be themselves sorted.  Losing that requirement means we can ignore all partitions that fall before '''or''' after the ''k''th place in the end.  We only recur in to the partition that actually contains the ''k''th element itself.

  '''function''' findFirstK(list, left, right, k)
      '''if''' right > left
          select a pivot value list[pivotIndex]
          pivotNewIndex := partition(list, left, right, pivotIndex)
          '''if''' pivotNewIndex > k  ''// new condition''
              findFirstK(list, left, pivotNewIndex-1, k)
          '''if''' pivotNewIndex < k
              findFirstK(list, pivotNewIndex+1, right, k)

The resulting algorithm requires an expected time of only O(''n''), which is just about the best any algorithm can hope for.

===Tournament Algorithm===
Another method is tournament algorithm. The idea is to conduct a knockout minimal round tournament to decide the ranks. It first organises the games(comparisons) between adjacent pairs and moves the winners to next round until championship(the first best) is decided. It also constructs the tournament tree along the way.  Now the second best element must be among the direct losers to winner and these losers can be found out by walking in the binary tree in O(log ''n'') time. It organises another tournament to decide the second best among these potential elements. The third best must be one among the losers of the second best in either of the two tournament trees. The approach continues until we find k elements. This algorithm takes O(n + k log ''n'') complexity, which for any fixed ''k'' independent of ''n'' is O(''n'').

== Lower bounds ==
In his seminal ''[[The Art of Computer Programming]]'', Don Knuth discussed a number of lower bounds for the number of comparisons required to locate the ''k'' smallest entries of an unorganized list of ''n'' items (using only comparisons). There's a trivial lower bound of ''n'' &minus; 1 for the minimum or maximum entry. To see this, consider a tournament where each game represents one comparison. Since every player except the winner of the tournament must lose a game before we know the winner, we have a lower bound of ''n'' &minus; 1 comparisons.

The story becomes more complex for other indexes. To find the ''k'' smallest values requires at least this many comparisons:

:<math>n - k + \sum_{n+1-k < j \leq n} \lceil{\operatorname{lg}\, j}\rceil</math>

This bound is achievable for ''k''=2 but better, more complex bounds exist for larger ''k''.

== Language support ==
Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. A notable exception is [[C++]], which provides a templated <code>nth_element</code> method with a guarantee of expected linear time. It is implied but not required that it is based on Hoare's algorithm by its requirement of expected linear time. (Ref section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E), see also [http://www.sgi.com/tech/stl/nth_element.html SGI STL description of nth_element])

C++ also provides the [http://www.sgi.com/tech/stl/partial_sort.html partial_sort] algorithm, which solves the problem of selecting the smallest ''k'' elements (sorted), with a time complexity of O(''n''log ''k''). No algorithm is provided for selecting the greatest ''k'' elements, but this can easily be achieved by inverting the ordering [[Predicate (computer programming)|predicate]].

For [[Perl]], the module [http://search.cpan.org/~salva/Sort-Key-Top Sort::Key::Top], available from [[CPAN]], provides a set of functions to select the top n elements from a list using several orderings and custom key extraction procedures.

Because [[sorting algorithm#Language support|language support for sorting]] is more ubiquitous, the simplistic approach of sorting followed by indexing is preferred in many environments despite its disadvantage in speed. Indeed for [[Lazy evaluation|lazy languages]], this simplistic approach can even get you the best complexity possible for the k smallest/greatest sorted (with maximum/minimum as a special case) if your sort is lazy enough.

== References ==
* [[Manuel Blum|M. Blum]], [[Robert Floyd|R.W. Floyd]], [[Vaughan Ronald Pratt|V. Pratt]], [[Ron Rivest|R. Rivest]] and [[Robert Tarjan|R. Tarjan]], "Time bounds for selection," ''J. Comput. System Sci''. 7 (1973) 448-461.
* [[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207&ndash;219.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp.183&ndash;196. Section 14.1: Dynamic order statistics, pp.302&ndash;308.
<references />

== External Links ==

* [http://www.ics.uci.edu/~eppstein/161/960130.html Design and Analysis of Algorithms], for a detailed explanation of the recurrence relation for the median-of-medians

[[Category:Algorithms]]

[[id:Algoritma seleksi]]
[[ja:選択アルゴリズム]]
[[pl:Selekcja (informatyka)]]