Date: Mon, 18 Apr 2016 16:49:13 +0200 From: Ed Schouten <ed@nuxi.nl> To: Hans Petter Selasky <hps@selasky.org> Cc: Aleksander Alekseev <afiskon@devzen.ru>, FreeBSD Current <freebsd-current@freebsd.org> Subject: Re: qsort() documentation Message-ID: <CABh_MKmE=p0Uq=p-zAD8i8AiWvTKDyeviviOE_piZVK%2BzHsbxA@mail.gmail.com> In-Reply-To: <5714DC98.7090208@selasky.org> References: <5714C86A.8050204@selasky.org> <20160418151639.634d571d@fujitsu> <5714DC98.7090208@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
2016-04-18 15:09 GMT+02:00 Hans Petter Selasky <hps@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@nuxi.nl> Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CABh_MKmE=p0Uq=p-zAD8i8AiWvTKDyeviviOE_piZVK%2BzHsbxA>