Date: Thu, 26 Aug 1999 09:20:46 -0700 (PDT) From: Christopher Seiwald <seiwald@perforce.com> To: a-wada@mars.dti.ne.jp Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: anybody love qsort.c? Message-ID: <199908261620.JAA03347@perforce.com> In-Reply-To: <199908251432.AA00055@a.mars.dti.ne.jp>
next in thread | previous in thread | raw e-mail | index | archive | help
Apparently, someone does love qsort. Akira Wada wrote: | I think it would be difficult, not impossible, to decide the threshold | (Christopher Seiwald said, "# swaps >= 1024", and Tim Vanderhoek suggested, | "a ratio: #comparisons : # swaps") and to what point of qsort, to make | isort bail back, effectively, without troubles, and covering every situations. The value 1024 is arbitrary, to be sure, but it is in a very safe range: at 0, the BSD addition of isort to Bentley's qsort is left intact; at infinity, it is entirely disabled. Any number in between will exhibit at worst the behavior of one of the two. The number selection doesn't have to be fancy: as Akira pointed out, my problem seems to be a fringe case that no one else has ever noted. I am therefore more or less selecting the # for me and my data. | Then an improvement would be : | (1) delete the switching to "isort by swap_cnt", | and add the routine detecting sorted completely. Actually, if the data is sorted then the isort does just as many comparisons (and the same zero swaps) as a sort detection routine. | (2) adding (1), make the partitioning logic symmetrical, | for dataset sorted in reversed order to be processed efficiently, | e.g. malloc(size) for pivot instead of "swap(a, pm)" | and some modifications required by this. This starts to get like real code. My intent is not to reengineer qsort, or at all challenge Bentley's algorithm or BSD's addition, but rather temper the latter with a safe, understandable (for me) alteration. By the way, thanks (Akira) for your very nice depiction of the problem of partially sorted data. Christopher 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?199908261620.JAA03347>