From owner-freebsd-hackers Mon Aug 23 6:43:37 1999 Delivered-To: freebsd-hackers@freebsd.org Received: from not.demophon.com (ns.demophon.com [193.65.70.13]) by hub.freebsd.org (Postfix) with ESMTP id EEC5315AB0 for ; Mon, 23 Aug 1999 06:43:25 -0700 (PDT) (envelope-from will@not.demophon.com) Received: (from will@localhost) by not.demophon.com (8.9.3/8.8.7) id QAA56303; Mon, 23 Aug 1999 16:43:01 +0300 (EEST) (envelope-from will) To: John-Mark Gurney Cc: hackers@freebsd.org Subject: Re: anybody love qsort.c? References: <199908182356.QAA09187@perforce.com> <19990818215311.49180@hydrogen.fircrest.net> From: Ville-Pertti Keinonen Date: 23 Aug 1999 16:43:00 +0300 In-Reply-To: gurney_j@efn.org's message of "19 Aug 1999 07:56:55 +0300" Message-ID: <863dxay5nf.fsf@not.demophon.com> Lines: 30 X-Mailer: Gnus v5.5/XEmacs 20.4 - "Emerald" Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG 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