Re: Peter Chen and Charles Bachman

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
>><genew_at_mail.ocis.net> wrote:
>>
>>>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:
>
>[snip]
>
>>>>> 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
>>>>>structured code.
>>>>
>>>>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
>>>>code.
>>>
>>> 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.
>>Opinion?
>
>[snipped code]
>
> 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 reply