Selection algorithm: Difference between revisions

Revision as of 09:05, 25 August 2013

Revision as of 09:08, 25 August 2013

Line 77:

This bound is achievable for ''t''=2 but better, more complex bounds are known for larger ''t''.

== Space complexity ==

{{empty-section}}

== 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, and also partitions the data, requiring that the ''n''th element be sorted into its correct place, elements before the ''n''th element are less than it, and elements after the ''n''th element are greater than it. It is implied but not required that it is based on Hoare's algorithm (or some variant) by its requirement of expected linear time. (Refand sectionpartitioning of data.<ref>Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E), see also </ref><ref>[http://www.sgi.com/tech/stl/nth_element.html nth_element], SGI STL description of nth_element])</ref>

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 since this should be done by inverting the ordering [[Predicate (computer programming)|predicate]].