Re: qsort() documentation

On 04/18/16 16:49, Ed Schouten wrote:
> 2016-04-18 15:09 GMT+02:00 Hans Petter Selasky <hps_at_selasky.org>:
>> On 04/18/16 14:16, Aleksander Alekseev wrote:
>>> I suggest also add a short description of how it was achieved
>>> (randomization?).
>>
>> I think the algorithm is switching to mergesort. I'll look up the paper and
>> add that correctly before commit.
>
> As a Dutch person, I know the answer to this.
>
> Instead of picking a fixed pivot or choosing one at random, it uses an
> approach called linear time median finding to find a pivot that is
> 'approximately median'. There are a couple of algorithms for this, but
> I think Bentley's qsort() uses this:
>
> https://en.wikipedia.org/wiki/Dutch_national_flag_problem
>

Hi,

Ryan: Yes, there is quadratic behaviour still, but I believe the order 
is limited. For the matter of the topic I added a counter for the swap() 
code in the insertion fallback algorithm, and for a set of 2048 integers 
I never saw the swap() count exceed this number. For a pre-sorted array, 
values around ~2047 and reverse sorted ~2043. For random input far less.

Citing the document "bentley93engineering.pdf", a footnote says:

<cite>
Of course, quadratic behavior is still possible. One can generate 
fiendish inputs by bugging Quicksort: Con-
sider key values to be unknown initially. In the code for selecting a 
partition element, assign values in increas-
ing order as unknown keys are encountered. In the partitioning code, 
make unknown keys compare high.
</cite>

Did anyone try to generate such a fiendish set of data, and see how 
quadratic the FreeBSD's qsort() becomes?

Another thread, possibly related:

http://postgresql.nabble.com/Why-do-we-still-perform-a-check-for-pre-sorted-input-within-qsort-variants-td5746526.html

--HPS