Talk:Selection algorithm/GA1

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

Reviewer: RoySmith (talk · contribs) 14:31, 5 August 2023 (UTC)[reply]

Starting review RoySmith (talk) 14:31, 5 August 2023 (UTC)[reply]

Problem statement

it should be possible to sort the values into an order from smallest to largest; for instance, they may be numbers... Maybe it's better to say "they may be real numbers", to explicitly exclude the non-orderable complex numbers.
- Computers cannot represent arbitrary real numbers. Changed from "numbers or ..." to "integers, floating-point numbers, or ...". —David Eppstein (talk) 20:41, 5 August 2023 (UTC)[reply]
some sources may assume that the values are all distinct from each other.... The word "source" could refer to "source code" or "a reference in the literature". I'm pretty sure you mean the later, but perhaps a different word would remove the ambiguity.
- Replaced by "works on this problem". —David Eppstein (talk) 20:41, 5 August 2023 (UTC)[reply]

Algorithms

selection of the kth smallest value in a collection of values can be performed very simply... Delete "very". Or maybe "very simply" -> "trivially".
- Removed both words. —David Eppstein (talk) 20:45, 5 August 2023 (UTC)[reply]
if the output of the sorting algorithm is an array, jump to its kth element... I assume the intent of "is an array" is that it's some data structure which can be indexed in constant time, not strictly an Array (data structure).
A careful design of these factories leads to an algorithm that, when applied to median-finding, uses at most 2.942 comparisons. I don't have access to the source; I assume it explains where 2.942 comes from. Is it feasible to give a short description here of how that mysterious number is derived?

Language support

Python ... A linear-time selection algorithm is not included. needs a better citation than a link to a code repository.
If a WP:RS is available, it would be interesting to explore why the STL and Python implementations differ (one provides O(1), the other doesn't). Is there something intrinsic to the languages which drove this? As an aside, I did a little hunting and was surprised to find that Java (or even guava) doesn't supply anything.

Approximate algorithms

As a thought for possible expansion, there's lots of places where you want "approximately the k-th largest". A search results page will want to return the k-th best matches but it's OK if that's approximate. If relaxing the exactness criteria gives to a significant speed improvement, that may be a good tradeoff. It would be interesting to explore variations on selection algorithms which allow this.

Specific GA criteria

MOS:LEADLENGTH argues for a longer lead. Personally, I think the lead is fine as is, but mentioning this for completeness.
Earwig didn't report any issues, and I didn't dig any further.
No problems with neutrality or stability.
Illustrations are relevant, captioned, and appropriately licensed.
@David Eppstein: OK, that's pretty much it, I'll toss it back to you to address the issues above. RoySmith (talk) 15:51, 5 August 2023 (UTC)[reply]
Thanks! I'm still traveling today but should have more time to work on this starting tomorrow. —David Eppstein (talk) 15:57, 5 August 2023 (UTC)[reply]