Re: random predicate function

[Tyler Smith <tyler.smith@eku.edu>]

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

> 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.

Ah, thanks. Makes perfect sense now that I think about it.

Tyler