Re: random predicate function

["Pascal J. Bourguignon" <pjb@informatimago.com>]

Tyler Smith <tyler.smith@eku.edu> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>
>>
>> You shoud not use sort to randomize, because it's suboptimal
>> [ O(n*log(n)) at best instead of O(n) ].
>>
>> And foremost, you should not use a predicate that is not a total order
>> because this usually gives invalid results.
>
> I don't know what a 'total order' means. Is the result of the predicate
> invalid or the actual sorting?

http://en.wikipedia.org/wiki/Total_order

Actually, it should even be a strict total order, that is, it must be a <
operator, not a <= operator.


If you have cycles such as:   a < b < a
then some sort algorithms may not terminate.
When sorting lists, some algorithms could truncate the result.


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.