public inbox for glibc-bugs@sourceware.org help / color / mirror / Atom feed
From: "laurent dot deniau at cern dot ch" <sourceware-bugzilla@sourceware.org> To: glibc-bugs@sources.redhat.com Subject: [Bug libc/7019] New: bug in _quicksort Date: Tue, 11 Nov 2008 01:58:00 -0000 [thread overview] Message-ID: <20081111015729.7019.laurent.deniau@cern.ch> (raw) The _quicksort (stdlib/qsort.c) function is called from the qsort function (merge sort from stdlib/msort.c) when the memory allocation required for merge sort fails, that is typically when the array to sort is huge (uncommon cases). The alternative solution base on in place quicksort should still be highly efficient. This function has a bug in the partitioning algorithm line 151 and 153 where the mid pointer used to point to the pivot is moved to the right_ptr (left_ptr) making the partitions algorithm broken (suboptimal): the left (right) partition (depending on the line) does not anymore guarantee to hold the values lesser (greater) than the pivot. The algorithm still works since the last stage sorting small subfiles is performed by an insertion sort on the full array, hence masking the effect of the bug but increasing the overall complexity. The correct algorithm with three-partitions improvement can be found in "Algorithm in C" from Sedgwick or in the slides "QuickSort is Optimal" also from Sedgwick. I actually use an improved version of this algorithm optimized for 'compare' instead of 'less' and using a pivot as the median-of-three- random values and network sorting for small sizes (<7). The resulting algorithm beats the merge sort of the libc both in speed and number of comparison in almost all cases by about 20-30%. Only almost fully sorted arrays require less comparisons with the merge sort (about 10-15% less) since it converges towards linear complexity O(n) while the quicksort remains in O(n.log n), but the speed of the quicksort remains better unless the compare function has a very high cost. Finally the three-partitioning quicksort gives much better result on array with many duplicated values. An actual implementation of this algorithm can be found in the file http://cos.cvs.sourceforge.net/viewvc/cos/CosStd/src/Array.c?view=markup line 1018 to 1122 (replace geval2(fun,a,b) by cmp(a,b) in the GCMP macro) regards. -- Summary: bug in _quicksort Product: glibc Version: unspecified Status: NEW Severity: normal Priority: P2 Component: libc AssignedTo: drepper at redhat dot com ReportedBy: laurent dot deniau at cern dot ch CC: glibc-bugs at sources dot redhat dot com http://sourceware.org/bugzilla/show_bug.cgi?id=7019 ------- You are receiving this mail because: ------- You are on the CC list for the bug, or are watching someone who is.
next reply other threads:[~2008-11-11 1:58 UTC|newest] Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top 2008-11-11 1:58 laurent dot deniau at cern dot ch [this message] 2008-11-11 2:04 ` [Bug libc/7019] " laurent dot deniau at cern dot ch
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20081111015729.7019.laurent.deniau@cern.ch \ --to=sourceware-bugzilla@sourceware.org \ --cc=glibc-bugs@sources.redhat.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).