🚀 go-pugleaf

In article <4gsb9l$46a@solutions.solon.com>
           schwarz@a3.complang.tuwien.ac.at "Konrad Schwarz" writes:

 > The qsort routine rearranges the array passed to it.  I don't think it
 > is possible for the comparision function to sort the real array 100 objects
 > further on in lockstep with the qsort routine, without relying on the
 > algorithm of qsort---which is implementation defined.  In this
 > case, the comparision function is not well-defined, since at some call,
 > a < b, later, a > b.

Right. Sorting in general only works if there is a well defined
and consistent ordering between the elements. If a>b and b>c then a>c must
be true. This transitive property must hold through any length of chain.

It seems that comparing the element addresses can fail for 3 reasons:

1. There is nothing stopping the algorithm moving elements even if the
   array is initially in order (example: heapsort)

2. There is no requirement that the pointers passed to the comparison
   function need point into the original array, so the comparison leads to
   undefined behaviour.

 > By the way, what is the relation of the ``quicker sort algorithm'' mentioned
 > in many manuals to the classic quick sort algorithm?  Is it best-of-three?

It is probably a median-of-3 pivot selection coupled with using an insertion
sort for small ranges of elements.

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------