Re: qsort() documentation

From: Ed Schouten <ed_at_nuxi.nl>
Date: Mon, 18 Apr 2016 16:49:13 +0200
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

-- 
Ed Schouten <ed_at_nuxi.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717
Received on Mon Apr 18 2016 - 12:49:14 UTC

This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:41:04 UTC