Anonymous user
Talk:Quickselect algorithm: Difference between revisions
→Scala implementation has a bug: new section
m (→How is pivot chosen?: bumped an indentation.) |
(→Scala implementation has a bug: new section) |
||
Line 22:
:: I also would suggest adding another part to the task requirement: ''Ensure (but do not show) that the program works with a single value.'' -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 10:56, 19 November 2013 (UTC)
== Scala implementation has a bug ==
Consider the input
quickSelect(Array(1, 1), 1)
The algorithm will loop infinitely. The reason is the pivot remains in the right partition, so if the pivot is the smallest element in the sequence, the recursive call will be on the same input. This is not too much of a problem if the elements in the right partition are different, because the pivot is chosen randomly so the next pivot might not be the smallest. But if the elements in the right partition are all the same the next pivot will be the same. Here is an implementation that does not use a random pivot, but fixes the bug: https://gist.github.com/jrraymond/602a12d4d648faf592473c80e8a6027b
| |||