imported>DreamRimmer bot II: Bot: Implementing outcome of RfC: converting list-defined references from {{reflist|refs=…}} to … for VisualEditor compatibility

2025-12-18T07:05:49Z

Bot: Implementing outcome of RfC: converting list-defined references from {{reflist|refs=…}} to <references>…</references> for VisualEditor compatibility

← Previous revision		Revision as of 07:05, 18 December 2025
Line 4:		Line 4:
	{{Use mdy dates\|cs1-dates=ly\|date=April 2023}}		{{Use mdy dates\|cs1-dates=ly\|date=April 2023}}
	{{Use list-defined references\|date=April 2023}}		{{Use list-defined references\|date=April 2023}}
	In [[computer science]], a '''selection algorithm''' is an [[algorithm]] for finding the <math>k</math>th smallest value in a collection of ~~ordered~~ values, such as numbers. The value that it finds is called the {{nowrap\|<math>k</math>th}} [[order statistic]]. Selection includes as special cases the problems of finding the [[minimum]], [[median]], and [[maximum]] element in the collection. Selection algorithms include [[quickselect]], and the [[median of medians]] algorithm. When applied to a collection of <math>n</math> values, these algorithms take [[linear time]], <math>O(n)</math> as expressed using [[big O notation]]. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted [[Array (data structure)\|array]] takes {{nowrap\|time <math>O(1)</math>.}}		In [[computer science]], a '''selection algorithm''' is an [[algorithm]] for finding the <math>k</math>th smallest value in a collection of orderable values, such as numbers. The value that it finds is called the {{nowrap\|<math>k</math>th}} [[order statistic]]. Selection includes as special cases the problems of finding the [[minimum]], [[median]], and [[maximum]] element in the collection. Selection algorithms include [[quickselect]], and the [[median of medians]] algorithm. When applied to a collection of <math>n</math> values, these algorithms take [[linear time]], <math>O(n)</math> as expressed using [[big O notation]]. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted [[Array (data structure)\|array]] takes {{nowrap\|time <math>O(1)</math>.}}

	==Problem statement==		==Problem statement==
Line 28:		Line 28:
	*If the pivot were exactly at the median of the input, then each recursive call would have at most half as many values as the previous call, and the total times would add in a [[geometric series]] {{nowrap\|to <math>O(n)</math>.}} However, finding the median is itself a selection problem, on the entire original input. Trying to find it by a recursive call to a selection algorithm would lead to an infinite recursion, because the problem size would not decrease in each {{nowrap\|call.{{r\|kletar}}}}		*If the pivot were exactly at the median of the input, then each recursive call would have at most half as many values as the previous call, and the total times would add in a [[geometric series]] {{nowrap\|to <math>O(n)</math>.}} However, finding the median is itself a selection problem, on the entire original input. Trying to find it by a recursive call to a selection algorithm would lead to an infinite recursion, because the problem size would not decrease in each {{nowrap\|call.{{r\|kletar}}}}
	*[[Quickselect]] chooses the pivot uniformly at random from the input values. It can be described as a [[prune and search]] algorithm,{{r\|gootam}} a variant of [[quicksort]], with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections <math>L</math> {{nowrap\|and <math>R</math>,}} quickselect only makes one of these two calls. Its [[expected time]] {{nowrap\|is <math>O(n)</math>.{{r\|clrs\|kletar\|gootam}}}} For any constant <math>C</math>, the probability that its number of comparisons exceeds <math>Cn</math> is superexponentially small {{nowrap\|in <math>C</math>.{{r\|devroye}}}}		*[[Quickselect]] chooses the pivot uniformly at random from the input values. It can be described as a [[prune and search]] algorithm,{{r\|gootam}} a variant of [[quicksort]], with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections <math>L</math> {{nowrap\|and <math>R</math>,}} quickselect only makes one of these two calls. Its [[expected time]] {{nowrap\|is <math>O(n)</math>.{{r\|clrs\|kletar\|gootam}}}} For any constant <math>C</math>, the probability that its number of comparisons exceeds <math>Cn</math> is superexponentially small {{nowrap\|in <math>C</math>.{{r\|devroye}}}}
	*The [[Floyd–Rivest algorithm]], a variation of quickselect, chooses a pivot by randomly sampling a subset of <math>r</math> data values, for some sample {{nowrap\|size <math>r</math>,}} and then recursively selecting two elements somewhat above and below position <math>rk/n</math> of the sample to use as pivots. With this choice, it is likely that <math>k</math> is sandwiched between the two pivots, so that after pivoting only a small number of data values between the pivots are left for a recursive call. This method can achieve an expected number of comparisons that is {{nowrap\|<math>n+\min(k,n-k)+o(n)</math>.{{r\|floriv}}}} In their original work, Floyd and Rivest claimed that the <math>o(n)</math> term could be made as small as <math>O(\sqrt n)</math> by a recursive sampling scheme, but the correctness of their analysis has been {{nowrap\|questioned.{{r\|brown\|prt}}}} Instead, more rigorous analysis has shown that a version of their algorithm achieves <math>O(\sqrt{n\log n})</math> for this {{nowrap\|term.{{r\|knuth}}}} Although the usual analysis of both quickselect and the Floyd–Rivest algorithm assumes the use of a [[true random number generator]], a version of the Floyd–Rivest algorithm using a [[pseudorandom number generator]] seeded with only logarithmically many true random bits has been proven to run in linear time with high probability.{{r\|karrag}}		*The [[Floyd–Rivest algorithm]], a variation of quickselect, chooses a pivot by randomly sampling a subset of <math>r</math> data values, for some sample {{nowrap\|size <math>r</math>,}} and then recursively selecting two elements somewhat above and below position <math>rk/n</math> of the sample to use as pivots. With this choice, it is likely that <math>k</math> is sandwiched between the two pivots, so that after pivoting only a small number of data values between the pivots are left for a recursive call. This method can achieve an expected number of comparisons that is {{nowrap\|<math>n+\min(k,n-k)+o(n)</math>.{{r\|floriv}}}} In their original work, Floyd and Rivest claimed that the <math>o(n)</math> term could be made as small as <math>O(\sqrt n)</math> by a recursive sampling scheme, but the correctness of their analysis has been {{nowrap\|questioned.{{r\|brown\|prt}}}} Instead, more rigorous analysis has shown that a version of their algorithm achieves <math>O(\sqrt{n\log n})</math> for this {{nowrap\|term.{{r\|knuth}}}} Although the usual analysis of both quickselect and the Floyd–Rivest algorithm assumes the use of a [[Hardware random number generator\|true random number generator]], a version of the Floyd–Rivest algorithm using a [[pseudorandom number generator]] seeded with only logarithmically many true random bits has been proven to run in linear time with high probability.{{r\|karrag}}
	[[File:Mid-of-mid.png\|thumb\|upright=1.35\|Visualization of pivot selection for the [[median of medians]] method. Each set of five elements is shown as a column of dots in the figure, sorted in increasing order from top to bottom. If their medians (the green and purple dots in the middle row) are sorted in increasing order from left to right, and the median of medians is chosen as the pivot, then the <math>3n/10</math> elements in the upper left quadrant will be less than the pivot, and the <math>3n/10</math> elements in the lower right quadrant will be greater than the pivot, showing that many elements will be eliminated by pivoting.]]		[[File:Mid-of-mid.png\|thumb\|upright=1.35\|Visualization of pivot selection for the [[median of medians]] method. Each set of five elements is shown as a column of dots in the figure, sorted in increasing order from top to bottom. If their medians (the green and purple dots in the middle row) are sorted in increasing order from left to right, and the median of medians is chosen as the pivot, then the <math>3n/10</math> elements in the upper left quadrant will be less than the pivot, and the <math>3n/10</math> elements in the lower right quadrant will be greater than the pivot, showing that many elements will be eliminated by pivoting.]]
	*The [[median of medians]] method partitions the input into sets of five elements, and uses some other non-recursive method to find the median of each of these sets in constant time per set. It then recursively calls itself to find the median of these <math>n/5</math> medians. Using the resulting median of medians as the pivot produces a partition with {{nowrap\|<math>\max(\|L\|,\|R\|)\le 7n/10</math>.}} Thus, a problem on <math>n</math> elements is reduced to two recursive problems on <math>n/5</math> elements (to find the pivot) and at most <math>7n/10</math> elements (after the pivot is used). The total size of these two recursive subproblems is at {{nowrap\|most <math>9n/10</math>,}} allowing the total time to be analyzed as a geometric series adding {{nowrap\|to <math>O(n)</math>.}} Unlike quickselect, this algorithm is deterministic, not {{nowrap\|randomized.{{r\|clrs\|erickson\|bfprt}}}} It was the first linear-time deterministic selection algorithm {{nowrap\|known,{{r\|bfprt}}}} and is commonly taught in undergraduate algorithms classes as an example of a [[Divide-and-conquer algorithm\|divide and conquer]] that does not divide into two equal {{nowrap\|subproblems.{{r\|clrs\|erickson\|gootam\|gurwitz}}}} However, the high constant factors in its <math>O(n)</math> time bound make it slower than quickselect in {{nowrap\|practice,{{r\|skiena\|gootam}}}} and slower even than sorting for inputs of moderate {{nowrap\|size.{{r\|erickson}}}}		*The [[median of medians]] method partitions the input into sets of five elements, and uses some other non-recursive method to find the median of each of these sets in constant time per set. It then recursively calls itself to find the median of these <math>n/5</math> medians. Using the resulting median of medians as the pivot produces a partition with {{nowrap\|<math>\max(\|L\|,\|R\|)\le 7n/10</math>.}} Thus, a problem on <math>n</math> elements is reduced to two recursive problems on <math>n/5</math> elements (to find the pivot) and at most <math>7n/10</math> elements (after the pivot is used). The total size of these two recursive subproblems is at {{nowrap\|most <math>9n/10</math>,}} allowing the total time to be analyzed as a geometric series adding {{nowrap\|to <math>O(n)</math>.}} Unlike quickselect, this algorithm is deterministic, not {{nowrap\|randomized.{{r\|clrs\|erickson\|bfprt}}}} It was the first linear-time deterministic selection algorithm {{nowrap\|known,{{r\|bfprt}}}} and is commonly taught in undergraduate algorithms classes as an example of a [[Divide-and-conquer algorithm\|divide and conquer]] that does not divide into two equal {{nowrap\|subproblems.{{r\|clrs\|erickson\|gootam\|gurwitz}}}} However, the high constant factors in its <math>O(n)</math> time bound make it slower than quickselect in {{nowrap\|practice,{{r\|skiena\|gootam}}}} and slower even than sorting for inputs of moderate {{nowrap\|size.{{r\|erickson}}}}
Line 76:		Line 76:

	== Language support ==		== 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~~ the [[Standard ~~Template Library~~]] ~~for~~ [[C++]]~~, which~~ provides a templated <code>nth_element</code> method with a guarantee of expected linear time.{{r\|skiena}}		Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. Notable exceptions are the [[Standard library\|standard libraries]] of [[C++]] and [[Rust (programming language)\|Rust]]. The [[Standard Template Library]] of C++ provides a templated <code>nth_element</code> method with a guarantee of expected linear time.{{r\|skiena}} Rust's standard library provides multiple variants of the <code>select_nth_unstable</code> member function for the <code>slice</code> data type. These variants all have guaranteed linear running time for all inputs.{{r\|rust}}

	[[Python (programming language)\|Python]]'s standard library includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> functions for returning the smallest or largest elements from a collection, in sorted order. The implementation maintains a [[binary heap]], limited to holding <math>k</math> elements, and initialized to the first <math>k</math> elements in the collection. Then, each subsequent item of the collection may replace the largest or smallest element in the heap if it is smaller or larger than this element. The algorithm's memory usage is superior to heapselect (the former only holds <math>k</math> elements in memory at a time while the latter requires manipulating the entire dataset into memory). Running time depends on data ordering. The best case is <math>O((n - k) + k\log k)</math> for already sorted data. The worst-case is <math>O(n\log k)</math> for reverse sorted data. In average cases, there are likely to be few heap updates and most input elements are processed with only a single comparison. For example, extracting the 100 largest or smallest values out of 10,000,000 random inputs makes 10,009,401 comparisons on average.{{r\|python}}		[[Python (programming language)\|Python]]'s standard library includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> functions for returning the smallest or largest elements from a collection, in sorted order. The implementation maintains a [[binary heap]], limited to holding <math>k</math> elements, and initialized to the first <math>k</math> elements in the collection. Then, each subsequent item of the collection may replace the largest or smallest element in the heap if it is smaller or larger than this element. The algorithm's memory usage is superior to heapselect (the former only holds <math>k</math> elements in memory at a time while the latter requires manipulating the entire dataset into memory). Running time depends on data ordering. The best case is <math>O((n - k) + k\log k)</math> for already sorted data. The worst-case is <math>O(n\log k)</math> for reverse sorted data. In average cases, there are likely to be few heap updates and most input elements are processed with only a single comparison. For example, extracting the 100 largest or smallest values out of 10,000,000 random inputs makes 10,009,401 comparisons on average.{{r\|python}}
Line 90:		Line 90:

	== References ==		== References ==
	~~{{reflist\|refs=~~		<references>

	<ref name=akss>{{cite journal		<ref name=akss>{{cite journal
	\| last1 = Ajtai \| first1 = Miklós \| author1-link = Miklós Ajtai		\| last1 = Ajtai \| first1 = Miklós \| author1-link = Miklós Ajtai
Line 546:		Line 545:
	<ref name=python>{{cite web\|url=https://github.com/python/cpython/blob/main/Lib/heapq.py\|title=heapq package source code\|work=Python library\|access-date=2023-08-06}}; see also the linked [https://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest/ comparison of algorithm performance on best-case data].</ref>		<ref name=python>{{cite web\|url=https://github.com/python/cpython/blob/main/Lib/heapq.py\|title=heapq package source code\|work=Python library\|access-date=2023-08-06}}; see also the linked [https://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest/ comparison of algorithm performance on best-case data].</ref>

	}}		<ref name=rust>{{cite web \|title=Primitive Type slice \|url=https://doc.rust-lang.org/std/primitive.slice.html#method.select_nth_unstable \|website=The Rust Standard Library \|access-date=12 October 2025}}</ref>
			</references>

	{{DEFAULTSORT:Selection Algorithm}}		{{DEFAULTSORT:Selection Algorithm}}
	[[Category:Selection algorithms\| ]]		[[Category:Selection algorithms\| ]]

imported>David Eppstein: Undid revision 1272462687 by 49.207.232.175 (talk) the values must have an ordering. They may not be presented in that ordering.

2025-01-28T20:59:59Z

Undid revision 1272462687 by 49.207.232.175 (talk) the values must have an ordering. They may not be presented in that ordering.

Show changes

← Previous revision		Revision as of 07:05, 18 December 2025
Line 4:		Line 4:
	{{Use mdy dates\|cs1-dates=ly\|date=April 2023}}		{{Use mdy dates\|cs1-dates=ly\|date=April 2023}}
	{{Use list-defined references\|date=April 2023}}		{{Use list-defined references\|date=April 2023}}
	In [[computer science]], a '''selection algorithm''' is an [[algorithm]] for finding the <math>k</math>th smallest value in a collection of ~~ordered~~ values, such as numbers. The value that it finds is called the {{nowrap\|<math>k</math>th}} [[order statistic]]. Selection includes as special cases the problems of finding the [[minimum]], [[median]], and [[maximum]] element in the collection. Selection algorithms include [[quickselect]], and the [[median of medians]] algorithm. When applied to a collection of <math>n</math> values, these algorithms take [[linear time]], <math>O(n)</math> as expressed using [[big O notation]]. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted [[Array (data structure)\|array]] takes {{nowrap\|time <math>O(1)</math>.}}		In [[computer science]], a '''selection algorithm''' is an [[algorithm]] for finding the <math>k</math>th smallest value in a collection of orderable values, such as numbers. The value that it finds is called the {{nowrap\|<math>k</math>th}} [[order statistic]]. Selection includes as special cases the problems of finding the [[minimum]], [[median]], and [[maximum]] element in the collection. Selection algorithms include [[quickselect]], and the [[median of medians]] algorithm. When applied to a collection of <math>n</math> values, these algorithms take [[linear time]], <math>O(n)</math> as expressed using [[big O notation]]. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted [[Array (data structure)\|array]] takes {{nowrap\|time <math>O(1)</math>.}}

	==Problem statement==		==Problem statement==
Line 28:		Line 28:
	*If the pivot were exactly at the median of the input, then each recursive call would have at most half as many values as the previous call, and the total times would add in a [[geometric series]] {{nowrap\|to <math>O(n)</math>.}} However, finding the median is itself a selection problem, on the entire original input. Trying to find it by a recursive call to a selection algorithm would lead to an infinite recursion, because the problem size would not decrease in each {{nowrap\|call.{{r\|kletar}}}}		*If the pivot were exactly at the median of the input, then each recursive call would have at most half as many values as the previous call, and the total times would add in a [[geometric series]] {{nowrap\|to <math>O(n)</math>.}} However, finding the median is itself a selection problem, on the entire original input. Trying to find it by a recursive call to a selection algorithm would lead to an infinite recursion, because the problem size would not decrease in each {{nowrap\|call.{{r\|kletar}}}}
	*[[Quickselect]] chooses the pivot uniformly at random from the input values. It can be described as a [[prune and search]] algorithm,{{r\|gootam}} a variant of [[quicksort]], with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections <math>L</math> {{nowrap\|and <math>R</math>,}} quickselect only makes one of these two calls. Its [[expected time]] {{nowrap\|is <math>O(n)</math>.{{r\|clrs\|kletar\|gootam}}}} For any constant <math>C</math>, the probability that its number of comparisons exceeds <math>Cn</math> is superexponentially small {{nowrap\|in <math>C</math>.{{r\|devroye}}}}		*[[Quickselect]] chooses the pivot uniformly at random from the input values. It can be described as a [[prune and search]] algorithm,{{r\|gootam}} a variant of [[quicksort]], with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections <math>L</math> {{nowrap\|and <math>R</math>,}} quickselect only makes one of these two calls. Its [[expected time]] {{nowrap\|is <math>O(n)</math>.{{r\|clrs\|kletar\|gootam}}}} For any constant <math>C</math>, the probability that its number of comparisons exceeds <math>Cn</math> is superexponentially small {{nowrap\|in <math>C</math>.{{r\|devroye}}}}
	*The [[Floyd–Rivest algorithm]], a variation of quickselect, chooses a pivot by randomly sampling a subset of <math>r</math> data values, for some sample {{nowrap\|size <math>r</math>,}} and then recursively selecting two elements somewhat above and below position <math>rk/n</math> of the sample to use as pivots. With this choice, it is likely that <math>k</math> is sandwiched between the two pivots, so that after pivoting only a small number of data values between the pivots are left for a recursive call. This method can achieve an expected number of comparisons that is {{nowrap\|<math>n+\min(k,n-k)+o(n)</math>.{{r\|floriv}}}} In their original work, Floyd and Rivest claimed that the <math>o(n)</math> term could be made as small as <math>O(\sqrt n)</math> by a recursive sampling scheme, but the correctness of their analysis has been {{nowrap\|questioned.{{r\|brown\|prt}}}} Instead, more rigorous analysis has shown that a version of their algorithm achieves <math>O(\sqrt{n\log n})</math> for this {{nowrap\|term.{{r\|knuth}}}} Although the usual analysis of both quickselect and the Floyd–Rivest algorithm assumes the use of a [[true random number generator]], a version of the Floyd–Rivest algorithm using a [[pseudorandom number generator]] seeded with only logarithmically many true random bits has been proven to run in linear time with high probability.{{r\|karrag}}		*The [[Floyd–Rivest algorithm]], a variation of quickselect, chooses a pivot by randomly sampling a subset of <math>r</math> data values, for some sample {{nowrap\|size <math>r</math>,}} and then recursively selecting two elements somewhat above and below position <math>rk/n</math> of the sample to use as pivots. With this choice, it is likely that <math>k</math> is sandwiched between the two pivots, so that after pivoting only a small number of data values between the pivots are left for a recursive call. This method can achieve an expected number of comparisons that is {{nowrap\|<math>n+\min(k,n-k)+o(n)</math>.{{r\|floriv}}}} In their original work, Floyd and Rivest claimed that the <math>o(n)</math> term could be made as small as <math>O(\sqrt n)</math> by a recursive sampling scheme, but the correctness of their analysis has been {{nowrap\|questioned.{{r\|brown\|prt}}}} Instead, more rigorous analysis has shown that a version of their algorithm achieves <math>O(\sqrt{n\log n})</math> for this {{nowrap\|term.{{r\|knuth}}}} Although the usual analysis of both quickselect and the Floyd–Rivest algorithm assumes the use of a [[Hardware random number generator\|true random number generator]], a version of the Floyd–Rivest algorithm using a [[pseudorandom number generator]] seeded with only logarithmically many true random bits has been proven to run in linear time with high probability.{{r\|karrag}}
	[[File:Mid-of-mid.png\|thumb\|upright=1.35\|Visualization of pivot selection for the [[median of medians]] method. Each set of five elements is shown as a column of dots in the figure, sorted in increasing order from top to bottom. If their medians (the green and purple dots in the middle row) are sorted in increasing order from left to right, and the median of medians is chosen as the pivot, then the <math>3n/10</math> elements in the upper left quadrant will be less than the pivot, and the <math>3n/10</math> elements in the lower right quadrant will be greater than the pivot, showing that many elements will be eliminated by pivoting.]]		[[File:Mid-of-mid.png\|thumb\|upright=1.35\|Visualization of pivot selection for the [[median of medians]] method. Each set of five elements is shown as a column of dots in the figure, sorted in increasing order from top to bottom. If their medians (the green and purple dots in the middle row) are sorted in increasing order from left to right, and the median of medians is chosen as the pivot, then the <math>3n/10</math> elements in the upper left quadrant will be less than the pivot, and the <math>3n/10</math> elements in the lower right quadrant will be greater than the pivot, showing that many elements will be eliminated by pivoting.]]
	*The [[median of medians]] method partitions the input into sets of five elements, and uses some other non-recursive method to find the median of each of these sets in constant time per set. It then recursively calls itself to find the median of these <math>n/5</math> medians. Using the resulting median of medians as the pivot produces a partition with {{nowrap\|<math>\max(\|L\|,\|R\|)\le 7n/10</math>.}} Thus, a problem on <math>n</math> elements is reduced to two recursive problems on <math>n/5</math> elements (to find the pivot) and at most <math>7n/10</math> elements (after the pivot is used). The total size of these two recursive subproblems is at {{nowrap\|most <math>9n/10</math>,}} allowing the total time to be analyzed as a geometric series adding {{nowrap\|to <math>O(n)</math>.}} Unlike quickselect, this algorithm is deterministic, not {{nowrap\|randomized.{{r\|clrs\|erickson\|bfprt}}}} It was the first linear-time deterministic selection algorithm {{nowrap\|known,{{r\|bfprt}}}} and is commonly taught in undergraduate algorithms classes as an example of a [[Divide-and-conquer algorithm\|divide and conquer]] that does not divide into two equal {{nowrap\|subproblems.{{r\|clrs\|erickson\|gootam\|gurwitz}}}} However, the high constant factors in its <math>O(n)</math> time bound make it slower than quickselect in {{nowrap\|practice,{{r\|skiena\|gootam}}}} and slower even than sorting for inputs of moderate {{nowrap\|size.{{r\|erickson}}}}		*The [[median of medians]] method partitions the input into sets of five elements, and uses some other non-recursive method to find the median of each of these sets in constant time per set. It then recursively calls itself to find the median of these <math>n/5</math> medians. Using the resulting median of medians as the pivot produces a partition with {{nowrap\|<math>\max(\|L\|,\|R\|)\le 7n/10</math>.}} Thus, a problem on <math>n</math> elements is reduced to two recursive problems on <math>n/5</math> elements (to find the pivot) and at most <math>7n/10</math> elements (after the pivot is used). The total size of these two recursive subproblems is at {{nowrap\|most <math>9n/10</math>,}} allowing the total time to be analyzed as a geometric series adding {{nowrap\|to <math>O(n)</math>.}} Unlike quickselect, this algorithm is deterministic, not {{nowrap\|randomized.{{r\|clrs\|erickson\|bfprt}}}} It was the first linear-time deterministic selection algorithm {{nowrap\|known,{{r\|bfprt}}}} and is commonly taught in undergraduate algorithms classes as an example of a [[Divide-and-conquer algorithm\|divide and conquer]] that does not divide into two equal {{nowrap\|subproblems.{{r\|clrs\|erickson\|gootam\|gurwitz}}}} However, the high constant factors in its <math>O(n)</math> time bound make it slower than quickselect in {{nowrap\|practice,{{r\|skiena\|gootam}}}} and slower even than sorting for inputs of moderate {{nowrap\|size.{{r\|erickson}}}}
Line 76:		Line 76:

	== Language support ==		== 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~~ the [[Standard ~~Template Library~~]] ~~for~~ [[C++]]~~, which~~ provides a templated <code>nth_element</code> method with a guarantee of expected linear time.{{r\|skiena}}		Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. Notable exceptions are the [[Standard library\|standard libraries]] of [[C++]] and [[Rust (programming language)\|Rust]]. The [[Standard Template Library]] of C++ provides a templated <code>nth_element</code> method with a guarantee of expected linear time.{{r\|skiena}} Rust's standard library provides multiple variants of the <code>select_nth_unstable</code> member function for the <code>slice</code> data type. These variants all have guaranteed linear running time for all inputs.{{r\|rust}}

	[[Python (programming language)\|Python]]'s standard library includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> functions for returning the smallest or largest elements from a collection, in sorted order. The implementation maintains a [[binary heap]], limited to holding <math>k</math> elements, and initialized to the first <math>k</math> elements in the collection. Then, each subsequent item of the collection may replace the largest or smallest element in the heap if it is smaller or larger than this element. The algorithm's memory usage is superior to heapselect (the former only holds <math>k</math> elements in memory at a time while the latter requires manipulating the entire dataset into memory). Running time depends on data ordering. The best case is <math>O((n - k) + k\log k)</math> for already sorted data. The worst-case is <math>O(n\log k)</math> for reverse sorted data. In average cases, there are likely to be few heap updates and most input elements are processed with only a single comparison. For example, extracting the 100 largest or smallest values out of 10,000,000 random inputs makes 10,009,401 comparisons on average.{{r\|python}}		[[Python (programming language)\|Python]]'s standard library includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> functions for returning the smallest or largest elements from a collection, in sorted order. The implementation maintains a [[binary heap]], limited to holding <math>k</math> elements, and initialized to the first <math>k</math> elements in the collection. Then, each subsequent item of the collection may replace the largest or smallest element in the heap if it is smaller or larger than this element. The algorithm's memory usage is superior to heapselect (the former only holds <math>k</math> elements in memory at a time while the latter requires manipulating the entire dataset into memory). Running time depends on data ordering. The best case is <math>O((n - k) + k\log k)</math> for already sorted data. The worst-case is <math>O(n\log k)</math> for reverse sorted data. In average cases, there are likely to be few heap updates and most input elements are processed with only a single comparison. For example, extracting the 100 largest or smallest values out of 10,000,000 random inputs makes 10,009,401 comparisons on average.{{r\|python}}
Line 90:		Line 90:

	== References ==		== References ==
	~~{{reflist\|refs=~~		<references>

	<ref name=akss>{{cite journal		<ref name=akss>{{cite journal
	\| last1 = Ajtai \| first1 = Miklós \| author1-link = Miklós Ajtai		\| last1 = Ajtai \| first1 = Miklós \| author1-link = Miklós Ajtai
Line 546:		Line 545:
	<ref name=python>{{cite web\|url=https://github.com/python/cpython/blob/main/Lib/heapq.py\|title=heapq package source code\|work=Python library\|access-date=2023-08-06}}; see also the linked [https://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest/ comparison of algorithm performance on best-case data].</ref>		<ref name=python>{{cite web\|url=https://github.com/python/cpython/blob/main/Lib/heapq.py\|title=heapq package source code\|work=Python library\|access-date=2023-08-06}}; see also the linked [https://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest/ comparison of algorithm performance on best-case data].</ref>

	}}		<ref name=rust>{{cite web \|title=Primitive Type slice \|url=https://doc.rust-lang.org/std/primitive.slice.html#method.select_nth_unstable \|website=The Rust Standard Library \|access-date=12 October 2025}}</ref>
			</references>

	{{DEFAULTSORT:Selection Algorithm}}		{{DEFAULTSORT:Selection Algorithm}}
	[[Category:Selection algorithms\| ]]		[[Category:Selection algorithms\| ]]

Selection algorithm - Revision history

imported>DreamRimmer bot II: Bot: Implementing outcome of RfC: converting list-defined references from {{reflist|refs=…}} to … for VisualEditor compatibility

imported>David Eppstein: Undid revision 1272462687 by 49.207.232.175 (talk) the values must have an ordering. They may not be presented in that ordering.