Boris Borcic wrote: > Paul Rubin wrote: >> Boris Borcic <[EMAIL PROTECTED]> writes: >>> x.sort(cmp = lambda x,y : cmp(random.random(),0.5)) >>> pick a random shuffle of x with uniform distribution ? >> >> You really can't assume anything like that. Sorting assumes an order >> relation on the items being sorted, which means if a < b and b < c, >> then a < c. If your comparison operation doesn't preserve that >> property then the sort algorithm could do anything, including looping >> forever or crashing. > > Not if it does the minimum number of comparisons to achieve the sort, in > which case it won't ever call cmp() if the result is pre-determined by > the order relation and previous comparisons, so that it will never get > from this comparison function a system of answers that's not consistent > with an order relation. That's obvious at least in the case where > random.random() == 0.5 never occurs (and at first sight even the latter > case shouldn't change it).
To be more convincing... assume the algorithm is optimal and calls cmp(x,y). Either the previous calls (+ assuming order relation) give no conclusion as to the possible result of the call, in which case the result can't contradict an order relation; or the previous calls (+assumption) provide only partial information; iow the algorithm knows for example x<=y and needs to determine which of x<y or x==y is the case; in which situation the comparison function could break the assumption of an order relation by answering eg "x>y". But is it possible for a sort algorithm assuming an order relation to attain eg x<=y but neither x<y nor x==y using calls to the comparison function involving either x or y and some other variables ? No, since the axiom of order applies to data that never has the form of weak inequalities and thus will never infer an inequality that's not strong. Ok, this isn't well written, but I have to run. Cheers, BB -- "On naît tous les mètres du même monde". -- http://mail.python.org/mailman/listinfo/python-list