Selection algorithm - Revision history

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.

← Previous revision		Revision as of 20:59, 28 January 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 ~~unordered~~ 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 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>.}}

	==Problem statement==		==Problem statement==

49.207.232.175: Corrected content to be more accurate. It is mentioned that ordered values. For understanding ordered values may be easier. But it can unordered also

2025-01-28T19:23:27Z

Corrected content to be more accurate. It is mentioned that ordered values. For understanding ordered values may be easier. But it can unordered also

← Previous revision		Revision as of 19:23, 28 January 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 unordered 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==

Aadirulez8: v2.05 - Autofix / Fix errors for CW project (Link equal to linktext)

2024-12-23T14:27:06Z

v2.05 - Autofix / Fix errors for CW project (Link equal to linktext)

← Previous revision		Revision as of 14:27, 23 December 2024
Line 78:		Line 78:
	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. 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}}

	[[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\|~~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}}

	Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}		Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}

Citation bot: Add: doi-access, isbn. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 39/188

2024-07-29T16:47:27Z

Add: doi-access, isbn. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 39/188

← Previous revision		Revision as of 16:47, 29 July 2024
Line 128:		Line 128:
	\| title = Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6–8, 1985, Providence, Rhode Island, USA		\| title = Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6–8, 1985, Providence, Rhode Island, USA
	\| year = 1985\| doi-access = free		\| year = 1985\| doi-access = free
			\| isbn = 0-89791-151-2
	}}</ref>		}}</ref>

Line 172:		Line 173:
	\| title = Space-Efficient Data Structures, Streams, and Algorithms – Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday		\| title = Space-Efficient Data Structures, Streams, and Algorithms – Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday
	\| volume = 8066		\| volume = 8066
	\| year = 2013}}</ref>		\| year = 2013\| isbn = 978-3-642-40272-2 }}</ref>

	<ref name=brown>{{cite journal		<ref name=brown>{{cite journal
Line 212:		Line 213:
	\| volume = 711		\| volume = 711
	\| year = 1993\| hdl = 11858/00-001M-0000-0014-B748-C		\| year = 1993\| hdl = 11858/00-001M-0000-0014-B748-C
			\| isbn = 978-3-540-57182-7
	\| hdl-access = free		\| hdl-access = free
	}}</ref>		}}</ref>
Line 420:		Line 422:
	\| title = 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA		\| title = 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA
	\| volume = 69		\| volume = 69
	\| year = 2019~~}}</ref>~~		\| year = 2019\| doi-access = free
			}}</ref>

	<ref name=kletar>{{cite book		<ref name=kletar>{{cite book
Line 474:		Line 477:
	\| publisher = IEEE Computer Society		\| publisher = IEEE Computer Society
	\| title = 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014		\| title = 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014
	\| year = 2014}}</ref>		\| year = 2014\| isbn = 978-1-4799-6517-5 }}</ref>

	<ref name=prt>{{cite journal		<ref name=prt>{{cite journal

71.41.4.149: /* Language support */ Missing word

2024-06-23T18:57:27Z

Language support: Missing word

← Previous revision		Revision as of 18:57, 23 June 2024
Line 78:		Line 78:
	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. 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}}

	[[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\|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 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\|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}}

	Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}		Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}

71.41.4.149: /* Language support */ Compare memory use with heapselect. Add best/worst/random case run times and a specific example.

2024-06-23T18:53:40Z

Language support: Compare memory use with heapselect. Add best/worst/random case run times and a specific example.

← Previous revision		Revision as of 18:53, 23 June 2024
Line 78:		Line 78:
	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. 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}}

	[[Python (programming language)\|Python]]'s standard library ~~(since 2.4)~~ includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> ~~subroutines~~ for returning the smallest or largest elements from a collection, in sorted order. ~~Different versions of Python have used different algorithms for these subroutines. As of Python version 3.13, 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 ~~items~~ of the collection may replace the largest or smallest element in the heap ~~(respectively~~ ~~for~~ ~~<code>heapq~~.~~nsmallest</code>~~ ~~and~~ <~~code~~>~~heapq.nlargest~~</~~code~~>) if it is ~~smaller~~ or ~~larger~~ ~~than~~ ~~this~~ ~~element~~. ~~The~~ ~~worst-case~~ time ~~for~~ ~~this~~ ~~implementation~~ is <math>O(n\log k)</math>, ~~worse~~ ~~than~~ ~~the~~ <math>O(n+k\log n)</math> ~~that~~ ~~would~~ ~~be achieved~~ ~~by heapselect~~. ~~However,~~ ~~for random~~ ~~input sequences~~, there are likely to be few heap updates and most input elements are processed with only a single comparison.{{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\|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 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}}

	Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}		Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}

Lklundin: /* Exact numbers of comparisons */ Knuth: First occurrence (and someone may not now)

2023-09-29T19:37:08Z

Exact numbers of comparisons: Knuth: First occurrence (and someone may not now)

← Previous revision		Revision as of 19:37, 29 September 2023
Line 60:		Line 60:
	== Exact numbers of comparisons ==		== Exact numbers of comparisons ==
	[[File:Median of 5.svg\|thumb\|upright=0.9\|Finding the median of five values using six comparisons. Each step shows the comparisons to be performed next as yellow line segments, and a [[Hasse diagram]] of the order relations found so far (with smaller=lower and larger=higher) as blue line segments. The red elements have already been found to be greater than three others and so cannot be the median. The larger of the two elements in the final comparison is the median.]]		[[File:Median of 5.svg\|thumb\|upright=0.9\|Finding the median of five values using six comparisons. Each step shows the comparisons to be performed next as yellow line segments, and a [[Hasse diagram]] of the order relations found so far (with smaller=lower and larger=higher) as blue line segments. The red elements have already been found to be greater than three others and so cannot be the median. The larger of the two elements in the final comparison is the median.]]
	Knuth supplies the following triangle of numbers summarizing pairs of <math>n</math> and <math>k</math> for which the exact number of comparisons needed by an optimal selection algorithm is known. The {{nowrap\|<math>n</math>th}} row of the triangle (starting with <math>n=1</math> in the top row) gives the numbers of comparisons for inputs of <math>n</math> values, and the {{nowrap\|<math>k</math>th}} number within each row gives the number of comparisons needed to select the {{nowrap\|<math>k</math>th}} smallest value from an input of that size. The rows are symmetric because selecting the {{nowrap\|<math>k</math>th}} smallest requires exactly the same number of comparisons, in the worst case, as selecting the {{nowrap\|<math>k</math>th}} {{nowrap\|largest.{{r\|knuth}}}}		[[Donald Knuth\|Knuth]] supplies the following triangle of numbers summarizing pairs of <math>n</math> and <math>k</math> for which the exact number of comparisons needed by an optimal selection algorithm is known. The {{nowrap\|<math>n</math>th}} row of the triangle (starting with <math>n=1</math> in the top row) gives the numbers of comparisons for inputs of <math>n</math> values, and the {{nowrap\|<math>k</math>th}} number within each row gives the number of comparisons needed to select the {{nowrap\|<math>k</math>th}} smallest value from an input of that size. The rows are symmetric because selecting the {{nowrap\|<math>k</math>th}} smallest requires exactly the same number of comparisons, in the worst case, as selecting the {{nowrap\|<math>k</math>th}} {{nowrap\|largest.{{r\|knuth}}}}

	{{center\|0}}		{{center\|0}}

David Eppstein: Undid revision 1173183558 by Patar knight (talk) Meaningless redundancy: "algorithm" is already in title and "computer science" follows from "algorithm". Short descriptions should be helpful in disambiguating searches; they should not be as vague and uninformative as possible.

2023-08-31T20:41:17Z

Undid revision 1173183558 by Patar knight (talk) Meaningless redundancy: "algorithm" is already in title and "computer science" follows from "algorithm". Short descriptions should be helpful in disambiguating searches; they should not be as vague and uninformative as possible.

← Previous revision		Revision as of 20:41, 31 August 2023
Line 1:		Line 1:
	{{Short description\|~~Computer~~ ~~science~~ ~~algorithim~~}}		{{Short description\|Method for finding kth smallest value}}
	{{For\|simulated natural selection in genetic algorithms\|Selection (genetic algorithm)}}		{{For\|simulated natural selection in genetic algorithms\|Selection (genetic algorithm)}}
	{{Good article}}		{{Good article}}

Patar knight: WP:SDJARGON

2023-08-31T20:20:25Z

WP:SDJARGON

← Previous revision		Revision as of 20:20, 31 August 2023
Line 1:		Line 1:
	{{Short description\|~~Method~~ ~~for~~ ~~finding kth smallest value~~}}		{{Short description\|Computer science algorithim}}
	{{For\|simulated natural selection in genetic algorithms\|Selection (genetic algorithm)}}		{{For\|simulated natural selection in genetic algorithms\|Selection (genetic algorithm)}}
	{{Good article}}		{{Good article}}

Chompy Ace at 13:43, 30 August 2023

2023-08-30T13:43:15Z

← Previous revision		Revision as of 13:43, 30 August 2023
Line 1:		Line 1:
⚫	{{~~good~~ article}}
	{{Short description\|Method for finding kth smallest value}}		{{Short description\|Method for finding kth smallest value}}
		⚫	{{For\|simulated natural selection in genetic algorithms\|Selection (genetic algorithm)}}
		⚫	{{Good article}}
	{{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}}
⚫	{{~~for~~\|simulated natural selection in genetic algorithms\|Selection (genetic algorithm)}}
	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 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>.}}

← Previous revision		Revision as of 14:27, 23 December 2024
Line 78:		Line 78:
	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. 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}}

	[[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\|~~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}}

	Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}		Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}

← Previous revision		Revision as of 18:57, 23 June 2024
Line 78:		Line 78:
	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. 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}}

	[[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\|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 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\|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}}

	Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}		Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}

← Previous revision		Revision as of 18:53, 23 June 2024
Line 78:		Line 78:
	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. 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}}

	[[Python (programming language)\|Python]]'s standard library ~~(since 2.4)~~ includes <code>heapq.nsmallest</code> and <code>heapq.nlargest</code> ~~subroutines~~ for returning the smallest or largest elements from a collection, in sorted order. ~~Different versions of Python have used different algorithms for these subroutines. As of Python version 3.13, 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 ~~items~~ of the collection may replace the largest or smallest element in the heap ~~(respectively~~ ~~for~~ ~~<code>heapq~~.~~nsmallest</code>~~ ~~and~~ <~~code~~>~~heapq.nlargest~~</~~code~~>) if it is ~~smaller~~ or ~~larger~~ ~~than~~ ~~this~~ ~~element~~. ~~The~~ ~~worst-case~~ time ~~for~~ ~~this~~ ~~implementation~~ is <math>O(n\log k)</math>, ~~worse~~ ~~than~~ ~~the~~ <math>O(n+k\log n)</math> ~~that~~ ~~would~~ ~~be achieved~~ ~~by heapselect~~. ~~However,~~ ~~for random~~ ~~input sequences~~, there are likely to be few heap updates and most input elements are processed with only a single comparison.{{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\|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 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}}

	Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}		Since 2017, [[Matlab]] has included <code>maxk()</code> and <code>mink()</code> functions, which return the maximal (minimal) <math>k</math> values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running {{nowrap\|time is.{{r\|matlab}}}}