Date: 23 Aug 1999 16:43:00 +0300 From: Ville-Pertti Keinonen <will@iki.fi> To: John-Mark Gurney <gurney_j@resnet.uoregon.edu> Cc: hackers@freebsd.org Subject: Re: anybody love qsort.c? Message-ID: <863dxay5nf.fsf@not.demophon.com> In-Reply-To: gurney_j@efn.org's message of "19 Aug 1999 07:56:55 %2B0300" References: <199908182356.QAA09187@perforce.com> <19990818215311.49180@hydrogen.fircrest.net>
next in thread | previous in thread | raw e-mail | index | archive | help
gurney_j@efn.org (John-Mark Gurney) writes: > Christopher Seiwald scribbled this message on Aug 18: > > It's a pretty straightforward change to bypass the insertion sort for > > large subsets of the data. If no one has a strong love for qsort, I'll > > educate myself on how to make and contribute this change. > > why don't you implement this w/ the 5 element median selection qsort > algorithm? my professor for cis413 talked about this algorithm and > that it really is the fastest qsort algorithm... I don't have any > pointers to a paper on this... but I might be able to dig some info up > on it if you are interested... I don't think the point is eliminating worst-cases, but optimizing common cases, which in this case caused more worst-cases and thus needs fixing. Besides, the median selection chooses among more than 3 elements already (but only when the data set is large enough). For fixing worst cases, an introspective sort might be a good idea, i.e. do a quick sort but fall back to heap sort if a certain depth is exceeded (you know you're losing when the depth exceeds log n). This also has another advantage - if you limit the depth of the sort, you don't need to use the cpu stack for state, you can allocate a fixed-size array for the purpose. This probably isn't a real performance advantage for a C qsort implementation because of the overhead of calling cmp. It does, however, guarantee that sorting uses a reasonable amount of stack. Such an assumption isn't portable when using qsort(3), though. Expect to die if you do large qsorts from threads with small thread stacks. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?863dxay5nf.fsf>