[ruby-core:70481] [Ruby trunk - Bug #11471] min, min_by, max, max_by with optional parameter return a wrong value

Issue #11471 has been updated by Helder Pereira.


I suppose I found the problem. Taking the first example:

~~~
[20, 32, 32, 21, 30, 25, 29, 13, 14].min(2)
~~~

This will call the function "nmin_run" in the file "enum.c", which sets "bufmax" to 4 times the number of minimums (n) we want (for the example, bufmax is 8), and then in the line [1327](https://github.com/ruby/ruby/blob/trunk/enum.c#L1327) will call the function "nmin_i" for each element of the original array.

In the function "nmin_i", when the buffer is full ("data->curlen == data->bufmax"), the function "nmin_filter" is called. In the example, that happens when curlen is 8, and so the buffer is [20, 32, 32, 21, 30, 25, 29, 13]. The "nmin_filter" will do a quicksort until the n smallest elements so far are on the  leftmost part of the buffer, and will discard the rest of the elements, which leaves us with [20, 13] in the buffer.

And now starts the problem. At the end of "nmin_filter" the limit (apparently with the intention of storing the greatest value in the buffer) is set to the last value in the buffer (in the example, 13), which is not true. And then based on that value "nmin_i" will discard all remaining elements greater than that (in the example, discarding the 14). The buffer is then sorted and it returns:

~~~
[13, 20]
~~~

So the solution is either remove all the limit-related part, or look into all elements that are on the right-side of the last pivot to calculate the limit.

----------------------------------------
Bug #11471: min, min_by, max, max_by with optional parameter return a wrong value
https://bugs.ruby-lang.org/issues/11471#change-53882

* Author: Tsuyoshi Sawada
* Status: Open
* Priority: Normal
* Assignee: 
* ruby -v: 
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN
----------------------------------------
This is reported in StackOverflow: http://stackoverflow.com/questions/32121749/why-20-13-14-min2-13-20. Sometimes `min`, `min_by`, `max`, `max_by` with an optional parameter return a wrong value.

    [20, 32, 32, 21, 30, 25, 29, 13, 14].min(2) # => [13, 20]
    [20, 32, 32, 21, 30, 25, 29, 13, 14].min_by(2, &:itself) # => [13, 20]
    [0, 0, 0, 0, 0, 0, 1, 3, 2].max(2) # => [3, 1]
    [0, 0, 0, 0, 0, 0, 1, 3, 2].max_by(2, &:itself) # => [3, 1]

---Files--------------------------------
enum_bug_fix.patch (2.05 KB)


-- 
https://bugs.ruby-lang.org/