Re: Peter Chen and Charles Bachman
Date: Tue, 15 Jun 2004 20:14:58 GMT
On Mon, 14 Jun 2004 09:04:37 -0700 in comp.databases.theory, Gene Wirchenko <genew_at_mail.ocis.net> wrote:
>Brian Inglis <Brian.Inglis_at_SystematicSw.Invalid> wrote:
>>On Mon, 07 Jun 2004 11:01:17 -0700 in comp.databases.theory, Gene Wirchenko
>>>Brian Inglis <Brian.Inglis_at_SystematicSw.Invalid> wrote:
>>>>On Tue, 25 May 2004 19:01:45 -0700 in comp.databases.theory, Gene
>>>>Wirchenko <genew_at_mail.ocis.net> wrote:
>>>>> One of the fast sorts has a structure whose symmetry wrt to two
>>>>>variables is obvious with a couple of gotos, but which is lost with
>>>>Are you perhaps referring to the quicksort partitioning step?
>>>>If solution symmetry is lost in "structured" code, blame the
>>>>programmer's poorly structured thinking, and not the poorly structured
>>> When the code is structured the symmetry is not in the code. The
>>>two variables appear quite different in use. Do you have a version
>>>that retains the symmetry IN THE CODE?
>>The only asymmetry below seems to be the optimization that requires
>>a specific order of operations to replace element swaps by moves.
> It has been over 20 years, it was an instructor's example, and I
>do not recall exactly which fast sort it was. Your code is way longer
>than I remember. I grant your code has good symmetry.
It was originally written to look similar and use similar structures
and variables to other types of sort routines, for an algorithms and
data structures course I taught: students probably learned more than
they ever wanted about sorting.
It's not as simple minded, straightforward, and problematic, as most academic examples tend to be: it's pretty close to production code. It also has useful comments, parameters for analysis and tuning, and instrumentation to allow analysis with a testbed and data generator. The elided code is almost the same volume again, to define and allow external parameter setting of static variables, and "skip_sort" routine for small partitions before a test run, tests to minimize worst case behaviour, and pick a median pivot.
-- Thanks. Take care, Brian Inglis Calgary, Alberta, Canada Brian.Inglis_at_CSi.com (Brian dot Inglis at SystematicSw dot ab dot ca) fake address use address above to replyReceived on Tue Jun 15 2004 - 22:14:58 CEST