Talk:Selection algorithm - Revision history

David Eppstein: /* Incorrect, unsourced (WP:OR?) illustration */ and

2024-08-31T23:19:57Z

Incorrect, unsourced (WP:OR?) illustration: and

← Previous revision		Revision as of 23:19, 31 August 2024
Line 347:		Line 347:
	::::::I was able to understand your illustration but only after basically re-inventing it myself. I think it needs more detail to be useful. [[User:John G Hasler\|John G Hasler]] ([[User talk:John G Hasler\|talk]]) 22:52, 31 August 2024 (UTC)		::::::I was able to understand your illustration but only after basically re-inventing it myself. I think it needs more detail to be useful. [[User:John G Hasler\|John G Hasler]] ([[User talk:John G Hasler\|talk]]) 22:52, 31 August 2024 (UTC)
	:::::::Such as?		:::::::Such as?
	:::::::Labeling the elements to make a decision tree, for instance, would be an obvious thing to try but in this instance it would miss the point. The point of the illustration is that after factoring out symmetries you don't need case analysis: there is only one choice of what your state looks like after each step. But adding labels would undo that factoring-out and give you many different cases (a tree with 127 nodes and 64 leaves, unlikely to be informative or readable). —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 23:18, 31 August 2024 (UTC)		:::::::Labeling the elements to make a decision tree, for instance, would be an obvious thing to try but in this instance it would miss the point. The point of the illustration is that after factoring out symmetries and forgetting the detailed ordering of eliminated elements you don't need case analysis: there is only one choice of what your state looks like after each step. But adding labels would undo that factoring-out and give you many different cases (a tree with 127 nodes and 64 leaves, unlikely to be informative or readable). —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 23:18, 31 August 2024 (UTC)

David Eppstein: /* Incorrect, unsourced (WP:OR?) illustration */ Reply

2024-08-31T23:18:13Z

Incorrect, unsourced (WP:OR?) illustration: Reply

← Previous revision		Revision as of 23:18, 31 August 2024
Line 346:		Line 346:
	::::::Thank you. I don't think my 1973 edition is quite the same as your 1998 one. While certainly relevant section 5.3.3 is much shorter and contains little about medians. One of the exercises is quite illuminating, though.		::::::Thank you. I don't think my 1973 edition is quite the same as your 1998 one. While certainly relevant section 5.3.3 is much shorter and contains little about medians. One of the exercises is quite illuminating, though.
	::::::I was able to understand your illustration but only after basically re-inventing it myself. I think it needs more detail to be useful. [[User:John G Hasler\|John G Hasler]] ([[User talk:John G Hasler\|talk]]) 22:52, 31 August 2024 (UTC)		::::::I was able to understand your illustration but only after basically re-inventing it myself. I think it needs more detail to be useful. [[User:John G Hasler\|John G Hasler]] ([[User talk:John G Hasler\|talk]]) 22:52, 31 August 2024 (UTC)
			:::::::Such as?
			:::::::Labeling the elements to make a decision tree, for instance, would be an obvious thing to try but in this instance it would miss the point. The point of the illustration is that after factoring out symmetries you don't need case analysis: there is only one choice of what your state looks like after each step. But adding labels would undo that factoring-out and give you many different cases (a tree with 127 nodes and 64 leaves, unlikely to be informative or readable). —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 23:18, 31 August 2024 (UTC)

John G Hasler: /* Incorrect, unsourced (WP:OR?) illustration */ Reply

2024-08-31T22:52:39Z

Incorrect, unsourced (WP:OR?) illustration: Reply

← Previous revision		Revision as of 22:52, 31 August 2024
Line 344:		Line 344:
	:::::Sure. Let me copy it from the references of the article for you:		:::::Sure. Let me copy it from the references of the article for you:
	:::::Knuth, Donald E. (1998). "Section 5.3.3: Minimum-comparison selection". The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 207–219. ISBN 0-201-89685-0. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 18:53, 30 August 2024 (UTC)		:::::Knuth, Donald E. (1998). "Section 5.3.3: Minimum-comparison selection". The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 207–219. ISBN 0-201-89685-0. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 18:53, 30 August 2024 (UTC)
			::::::Thank you. I don't think my 1973 edition is quite the same as your 1998 one. While certainly relevant section 5.3.3 is much shorter and contains little about medians. One of the exercises is quite illuminating, though.
			::::::I was able to understand your illustration but only after basically re-inventing it myself. I think it needs more detail to be useful. [[User:John G Hasler\|John G Hasler]] ([[User talk:John G Hasler\|talk]]) 22:52, 31 August 2024 (UTC)

David Eppstein: /* Incorrect, unsourced (WP:OR?) illustration */ Reply

2024-08-30T18:53:35Z

Incorrect, unsourced (WP:OR?) illustration: Reply

← Previous revision		Revision as of 18:53, 30 August 2024
Line 342:		Line 342:
	::::As an engineer designing median filters and using this article to better understand selection algorithms, I find the illustration incomprehensible. Could you provide a more specific reference than "the one we use is Knuth"?		::::As an engineer designing median filters and using this article to better understand selection algorithms, I find the illustration incomprehensible. Could you provide a more specific reference than "the one we use is Knuth"?
	::::[[User:John G Hasler\|John G Hasler]] ([[User talk:John G Hasler\|talk]]) 14:36, 30 August 2024 (UTC)		::::[[User:John G Hasler\|John G Hasler]] ([[User talk:John G Hasler\|talk]]) 14:36, 30 August 2024 (UTC)
			:::::Sure. Let me copy it from the references of the article for you:
			:::::Knuth, Donald E. (1998). "Section 5.3.3: Minimum-comparison selection". The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 207–219. ISBN 0-201-89685-0. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 18:53, 30 August 2024 (UTC)

John G Hasler: /* Incorrect, unsourced (WP:OR?) illustration */ Reply

2024-08-30T14:36:36Z

Incorrect, unsourced (WP:OR?) illustration: Reply

← Previous revision		Revision as of 14:36, 30 August 2024
Line 340:		Line 340:
	::OK. What is not self-evident and what seems to be missing from the illustration, is what exactly is swapped following a comparison. One (natural?) assumption, that just the two nodes connected by the yellow line segment are (conditionally) swapped, is not correct per my uploaded image. From your additional comments (and the logic of the problem), I now understand that in line two and in line four, what is (conditionally) swapped is pairs of nodes connected by a vertical line segment. Nevertheless, in line three still only two nodes are swapped. This is apparently so because although the left node has a vertical connection, its connecting node has been discarded (and marked as red). The idea of this illustration and the plenty of information it gives is a good one, but if the illustration is not clear to me then others may be confused as well. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 19:17, 30 September 2023 (UTC)		::OK. What is not self-evident and what seems to be missing from the illustration, is what exactly is swapped following a comparison. One (natural?) assumption, that just the two nodes connected by the yellow line segment are (conditionally) swapped, is not correct per my uploaded image. From your additional comments (and the logic of the problem), I now understand that in line two and in line four, what is (conditionally) swapped is pairs of nodes connected by a vertical line segment. Nevertheless, in line three still only two nodes are swapped. This is apparently so because although the left node has a vertical connection, its connecting node has been discarded (and marked as red). The idea of this illustration and the plenty of information it gives is a good one, but if the illustration is not clear to me then others may be confused as well. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 19:17, 30 September 2023 (UTC)
	:::Nothing is swapped. The comparisons are made between the elements indicated in yellow. Once those comparisons are made, a partially-ordered set isomorphic to the next one in the sequence results. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 20:23, 30 September 2023 (UTC)		:::Nothing is swapped. The comparisons are made between the elements indicated in yellow. Once those comparisons are made, a partially-ordered set isomorphic to the next one in the sequence results. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 20:23, 30 September 2023 (UTC)
			::::As an engineer designing median filters and using this article to better understand selection algorithms, I find the illustration incomprehensible. Could you provide a more specific reference than "the one we use is Knuth"?
			::::[[User:John G Hasler\|John G Hasler]] ([[User talk:John G Hasler\|talk]]) 14:36, 30 August 2024 (UTC)

Qwerfjkl (bot): Implementing WP:PIQA (Task 26)

2024-02-07T09:27:51Z

Implementing WP:PIQA (Task 26)

← Previous revision		Revision as of 09:27, 7 February 2024
Line 1:		Line 1:
	{{GA\|15:55, 6 August 2023 (UTC)\|topic=Computing and engineering\|page=1\|oldid=1168906485}}		{{GA\|15:55, 6 August 2023 (UTC)\|topic=Computing and engineering\|page=1\|oldid=1168906485}}
⚫	{{WikiProject Computer science\|importance=mid~~\|class=GA~~}}
	{{DYK talk\|30 August\|2023\|entry=... that the study of '''[[selection algorithm]]s''' has been traced to an 1883 work of [[Lewis Carroll]] on how to award second place in [[single-elimination tournament]]s?\|nompage=Template:Did you know nominations/Selection algorithm}}		{{DYK talk\|30 August\|2023\|entry=... that the study of '''[[selection algorithm]]s''' has been traced to an 1883 work of [[Lewis Carroll]] on how to award second place in [[single-elimination tournament]]s?\|nompage=Template:Did you know nominations/Selection algorithm}}
			{{WikiProject banner shell\|class=GA\|
		⚫	{{WikiProject Computer science\|importance=mid}}
			}}

	== No mention of min-max heap as a linear time selection algorithm ==		== No mention of min-max heap as a linear time selection algorithm ==

David Eppstein: /* Incorrect, unsourced (WP:OR?) illustration */ Reply

2023-09-30T20:23:57Z

Incorrect, unsourced (WP:OR?) illustration: Reply

← Previous revision		Revision as of 20:23, 30 September 2023
Line 337:		Line 337:
	:(After comparing the top elements 3 and 4 of the 2-3 and 3-4 pairs, we add an adge from 3 up to 4 but leave the 2-3 and 3-4 pairs as they are; where does your 3-3 edge come from?) There are many sources for a six-comparison five-element median; the one we use is Knuth. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 16:06, 30 September 2023 (UTC)		:(After comparing the top elements 3 and 4 of the 2-3 and 3-4 pairs, we add an adge from 3 up to 4 but leave the 2-3 and 3-4 pairs as they are; where does your 3-3 edge come from?) There are many sources for a six-comparison five-element median; the one we use is Knuth. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 16:06, 30 September 2023 (UTC)
	::OK. What is not self-evident and what seems to be missing from the illustration, is what exactly is swapped following a comparison. One (natural?) assumption, that just the two nodes connected by the yellow line segment are (conditionally) swapped, is not correct per my uploaded image. From your additional comments (and the logic of the problem), I now understand that in line two and in line four, what is (conditionally) swapped is pairs of nodes connected by a vertical line segment. Nevertheless, in line three still only two nodes are swapped. This is apparently so because although the left node has a vertical connection, its connecting node has been discarded (and marked as red). The idea of this illustration and the plenty of information it gives is a good one, but if the illustration is not clear to me then others may be confused as well. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 19:17, 30 September 2023 (UTC)		::OK. What is not self-evident and what seems to be missing from the illustration, is what exactly is swapped following a comparison. One (natural?) assumption, that just the two nodes connected by the yellow line segment are (conditionally) swapped, is not correct per my uploaded image. From your additional comments (and the logic of the problem), I now understand that in line two and in line four, what is (conditionally) swapped is pairs of nodes connected by a vertical line segment. Nevertheless, in line three still only two nodes are swapped. This is apparently so because although the left node has a vertical connection, its connecting node has been discarded (and marked as red). The idea of this illustration and the plenty of information it gives is a good one, but if the illustration is not clear to me then others may be confused as well. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 19:17, 30 September 2023 (UTC)
			:::Nothing is swapped. The comparisons are made between the elements indicated in yellow. Once those comparisons are made, a partially-ordered set isomorphic to the next one in the sequence results. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 20:23, 30 September 2023 (UTC)

Lklundin: /* Incorrect, unsourced (WP:OR?) illustration */ r

2023-09-30T19:17:52Z

Incorrect, unsourced (WP:OR?) illustration: r

← Previous revision		Revision as of 19:17, 30 September 2023
Line 336:		Line 336:
	2		2
	:(After comparing the top elements 3 and 4 of the 2-3 and 3-4 pairs, we add an adge from 3 up to 4 but leave the 2-3 and 3-4 pairs as they are; where does your 3-3 edge come from?) There are many sources for a six-comparison five-element median; the one we use is Knuth. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 16:06, 30 September 2023 (UTC)		:(After comparing the top elements 3 and 4 of the 2-3 and 3-4 pairs, we add an adge from 3 up to 4 but leave the 2-3 and 3-4 pairs as they are; where does your 3-3 edge come from?) There are many sources for a six-comparison five-element median; the one we use is Knuth. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 16:06, 30 September 2023 (UTC)
			::OK. What is not self-evident and what seems to be missing from the illustration, is what exactly is swapped following a comparison. One (natural?) assumption, that just the two nodes connected by the yellow line segment are (conditionally) swapped, is not correct per my uploaded image. From your additional comments (and the logic of the problem), I now understand that in line two and in line four, what is (conditionally) swapped is pairs of nodes connected by a vertical line segment. Nevertheless, in line three still only two nodes are swapped. This is apparently so because although the left node has a vertical connection, its connecting node has been discarded (and marked as red). The idea of this illustration and the plenty of information it gives is a good one, but if the illustration is not clear to me then others may be confused as well. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 19:17, 30 September 2023 (UTC)

David Eppstein: /* Incorrect, unsourced (WP:OR?) illustration */ r

2023-09-30T16:06:45Z

Incorrect, unsourced (WP:OR?) illustration: r

← Previous revision		Revision as of 16:06, 30 September 2023
Line 329:		Line 329:
	[[File:5-Median-fail.jpg\|thumb\|Failed attempt to determine the median of five values using six comparisons]]		[[File:5-Median-fail.jpg\|thumb\|Failed attempt to determine the median of five values using six comparisons]]
	This article has an illustration from editor {{u\|David Eppstein}} that claims to illustrate how a 5-sample median can be determined using six comparisons. The underlying selection algorithm is unsourced. Either the algorithm is not well enough explained (which therefore needs to be fixed) or it does in fact not work. The specific 5-sample sequence (3,4,2,3,2) has the median 3, but for this example the provided algorithm appears to yield the incorrect number 2. Someone please either clarify the algorithm or remove the illustration if it is - as I suspect - in fact not describing a valid, general method for determining a 5-sample median. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 14:31, 30 September 2023 (UTC)		This article has an illustration from editor {{u\|David Eppstein}} that claims to illustrate how a 5-sample median can be determined using six comparisons. The underlying selection algorithm is unsourced. Either the algorithm is not well enough explained (which therefore needs to be fixed) or it does in fact not work. The specific 5-sample sequence (3,4,2,3,2) has the median 3, but for this example the provided algorithm appears to yield the incorrect number 2. Someone please either clarify the algorithm or remove the illustration if it is - as I suspect - in fact not describing a valid, general method for determining a 5-sample median. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 14:31, 30 September 2023 (UTC)
			:Your illustration performs the algorithm incorrectly. The third line should look like
			4
			/ \
			3 3 2
			\|
			2
			:(After comparing the top elements 3 and 4 of the 2-3 and 3-4 pairs, we add an adge from 3 up to 4 but leave the 2-3 and 3-4 pairs as they are; where does your 3-3 edge come from?) There are many sources for a six-comparison five-element median; the one we use is Knuth. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 16:06, 30 September 2023 (UTC)

Lklundin: /* Incorrect, unsourced (WP:OR?) illustration */ new section

2023-09-30T14:31:53Z

Incorrect, unsourced (WP:OR?) illustration: new section

← Previous revision		Revision as of 14:31, 30 September 2023
Line 324:		Line 324:
	==Did you know nomination==		==Did you know nomination==
	{{Template:Did you know nominations/Selection algorithm}}		{{Template:Did you know nominations/Selection algorithm}}

			== Incorrect, unsourced ([[WP:OR]]?) illustration ==

			[[File:5-Median-fail.jpg\|thumb\|Failed attempt to determine the median of five values using six comparisons]]
			This article has an illustration from editor {{u\|David Eppstein}} that claims to illustrate how a 5-sample median can be determined using six comparisons. The underlying selection algorithm is unsourced. Either the algorithm is not well enough explained (which therefore needs to be fixed) or it does in fact not work. The specific 5-sample sequence (3,4,2,3,2) has the median 3, but for this example the provided algorithm appears to yield the incorrect number 2. Someone please either clarify the algorithm or remove the illustration if it is - as I suspect - in fact not describing a valid, general method for determining a 5-sample median. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 14:31, 30 September 2023 (UTC)

← Previous revision		Revision as of 20:23, 30 September 2023
Line 337:		Line 337:
	:(After comparing the top elements 3 and 4 of the 2-3 and 3-4 pairs, we add an adge from 3 up to 4 but leave the 2-3 and 3-4 pairs as they are; where does your 3-3 edge come from?) There are many sources for a six-comparison five-element median; the one we use is Knuth. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 16:06, 30 September 2023 (UTC)		:(After comparing the top elements 3 and 4 of the 2-3 and 3-4 pairs, we add an adge from 3 up to 4 but leave the 2-3 and 3-4 pairs as they are; where does your 3-3 edge come from?) There are many sources for a six-comparison five-element median; the one we use is Knuth. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 16:06, 30 September 2023 (UTC)
	::OK. What is not self-evident and what seems to be missing from the illustration, is what exactly is swapped following a comparison. One (natural?) assumption, that just the two nodes connected by the yellow line segment are (conditionally) swapped, is not correct per my uploaded image. From your additional comments (and the logic of the problem), I now understand that in line two and in line four, what is (conditionally) swapped is pairs of nodes connected by a vertical line segment. Nevertheless, in line three still only two nodes are swapped. This is apparently so because although the left node has a vertical connection, its connecting node has been discarded (and marked as red). The idea of this illustration and the plenty of information it gives is a good one, but if the illustration is not clear to me then others may be confused as well. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 19:17, 30 September 2023 (UTC)		::OK. What is not self-evident and what seems to be missing from the illustration, is what exactly is swapped following a comparison. One (natural?) assumption, that just the two nodes connected by the yellow line segment are (conditionally) swapped, is not correct per my uploaded image. From your additional comments (and the logic of the problem), I now understand that in line two and in line four, what is (conditionally) swapped is pairs of nodes connected by a vertical line segment. Nevertheless, in line three still only two nodes are swapped. This is apparently so because although the left node has a vertical connection, its connecting node has been discarded (and marked as red). The idea of this illustration and the plenty of information it gives is a good one, but if the illustration is not clear to me then others may be confused as well. Thanks. [[User:Lklundin\|Lklundin]] ([[User talk:Lklundin\|talk]]) 19:17, 30 September 2023 (UTC)
			:::Nothing is swapped. The comparisons are made between the elements indicated in yellow. Once those comparisons are made, a partially-ordered set isomorphic to the next one in the sequence results. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 20:23, 30 September 2023 (UTC)