Talk:Quickselect algorithm

How is pivot chosen?

Should the task specify how the pivot is to be chosen? Or should it leave it up to the implementer (and perhaps specify explicitly that the implementer can choose it how they want)? For example, the Python implementation chooses a random pivot, so it is randomized quickselect. There are other ones, e.g. choose the first element, or median of three, etc. --Spoon! (talk) 01:23, 1 October 2013 (UTC)

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 :-)
--Paddy3118 (talk) 22:06, 2 October 2013 (UTC)

C# and Quicksort

The C# solution also includes quicksort for which we already have a task. I think it would be better if C# concentrated on just what was needed for Quickselect in its codem to aid in language comparisons. -Paddy3118 (talk) 04:20, 6 October 2013 (UTC)

C# solution sorting is done by LINQ OrderBy method. It really doesn't talk about how sorting is implemented (it is hidden by OrderBy method - and actually I don't know what kind method OrderBy is using). Goal was to show important feature of QuickSelect - it sorts elements such way that elements before pivot index are smaller or equal than value stored to pivot index and vice versa. However, those elementes are not sorteed. So for e.g. if you have stored employee information to somekind array structure and want to get list of 100 smallest paid employees - without actually sorting employees based on their salary - then you could use QuickSelect algorithm. --Mpuonti (talk) 06:23, 6 October 2013 (UTC)

Thanks Mpuonti for pointing out the obvious - in a good way! Of course what is to the 'left' of the pivot are smaller, I just dismissed that in getting the algorithm working, which was done before I set the task goal where the idea of the test was to provide an easy check that the algorithm worked.

Unwittingly, the test does allow for optimisations, but I was hoping for examples that concentrated on getting the basic algorithm working correctly.

Task writing has its quirks. Thanks for the learning experience :-)
-Paddy3118 (talk) 06:39, 6 October 2013 (UTC)

Task Testing Values

In future tasks I suggest you to propose common task data values like [90, 80, 70, 60, 50, 0, 10, 20, 30, 40] instead of [9, 8, 7, 6, 5, 0, 1, 2, 3, 4] because with the first it's a little less easy to produce a correct output in presence of code bugs. Also to reduce the probability of having buggy entries that give a correct answer on just the common task data values, I suggest to offer more test cases.