Re: Function to find the greatest or smallest value

On 24/04/2009, at 10:56 PM, Asher613Smith@xxxxxxx wrote:

I may stand corrected. Or maybe not. Needs more investigation, because I
know that doing a test on each pass through the loop is costly. The sort can
be optimized.

Doesn't need any investigation at all. Consider how any sort works. It must compare at least two elements to determine their relative order. It must perform a comparison on all elements being sorted. It may perform that comparison multiple time because each comparison may result in a change to the elements ordinal position.

Even if the low-level code unrolls (i.e., optimises) the loop into a sequential set of operations it still has to perform a comparison on all the elements.

This is true for any kind of sort (exchange, selection, insertion, enumeration, etc.) The only real difference between these sorts is what they do with the result of the comparison.

A comparison is a test--exactly the same as an IF test in your own code-- thus a sort of any description will cost at least as much as testing the elements directly in your own code.

Even a special-purpose sort that is optimised for the particular data in question cannot perform faster than O(n). For a general-purpose sort that will only happen if the elements are already in the correct sequence.

Now if you can create a general-purpose sort that is faster than O(n) then patent it and make your fortune.

Regards,
Simon Coulter.
--------------------------------------------------------------------
FlyByNight Software OS/400, i5/OS Technical Specialists

http://www.flybynight.com.au/
Phone: +61 2 6657 8251 Mobile: +61 0411 091 400 /"\
Fax: +61 2 6657 8251 \ /
X
ASCII Ribbon campaign against HTML E-Mail / \
--------------------------------------------------------------------