Anonymous user
Talk:Quickselect algorithm: Difference between revisions
→Scala implementation has a bug: new section
m (→Task Testing Values: added a possible addition. -- ~~~~) |
(→Scala implementation has a bug: new section) |
||
| (3 intermediate revisions by one other user not shown) | |||
Line 5:
:Yep I saw that too, but thought I would just leave it open. It would allow some one to write an additional (or extend the current) Python solution using other pivot choices. I guess if it means a lot to someone then this is the time to create a separate task if they think it is necessary then restrict this task to be for random pivots, but I didn't think it was needed (which sounds better than I am lazy, however I can't truly remember if laziness applied in this case :-)<br>--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 22:06, 2 October 2013 (UTC)
:: I saw one program that used a random number, which I used initially in the REXX solution. But I found that using a midpoint was slightly faster, and the method bypasses using the '''random''' BIF (when generating a random number). -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 10:49, 19 November 2013 (UTC)
==C# and Quicksort==
Line 21:
:It is a compromise. I had to give some values from when the task was created and chose the ones I did to at least have a common set of values that were easy to check by eye. At the time of writing, I wanted something, rather than nothing at all. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 13:14, 11 October 2013 (UTC)
:: 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
| |||