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
read "by /the assumption of an order relation/ and previous comparisons" > 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). - this - the idea that /if/ the algorithm was optimal it would only sample the random comparison function up to a system of answers consistent with an order relation - is actually what prompted my question, iow "is it good for anything ?" Best, BB -- "On naît tous les mètres du même monde" -- http://mail.python.org/mailman/listinfo/python-list
