I wrote :
>
> ...in this sense, it is clear that quicksort for instance is optimal*
>
> It is easy to see, when you detail this algorithm, that never during its
> run is the result of a comparison it makes, preordained by comparisons
> already made; iow : it doesn't make superfluous or redundan
Paul Rubin wrote:
> Boris Borcic <[EMAIL PROTECTED]> writes:
>> To be more convincing... assume the algorithm is optimal and calls
>
> That assumption is not even slightly realistic. Real-world sorting
> algorithms almost never do a precisely minimal amount of comparison.
'optimal' or 'minimal a
Ross Ridge wrote:
> David G. Wonnacott wrote:
> > Couldn't we easily get an n*log(n) shuffle...
>
> Why are you trying to get an O(n*log(n)) shuffle when an O(n) shuffle
> algorithim is well known and implemented in Python as random.shuffle()?
I think David is referring to this: "don't you still n
David G. Wonnacott wrote:
> Couldn't we easily get an n*log(n) shuffle...
Why are you trying to get an O(n*log(n)) shuffle when an O(n) shuffle
algorithim is well known and implemented in Python as random.shuffle()?
Ross Ridge
--
http://mail.python.org/mailman/listinfo/
David G. Wonnacott wrote:
> From: "danielx" <[EMAIL PROTECTED]>
>Date: 22 Jul 2006 01:43:30 -0700
>
>Boris Borcic wrote:
>> does
>>
>> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>>
>> pick a random shuffle of x with uniform distribution ?
>
> ...
>
>Let e be
From: "danielx" <[EMAIL PROTECTED]>
Date: 22 Jul 2006 01:43:30 -0700
Boris Borcic wrote:
> does
>
> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>
> pick a random shuffle of x with uniform distribution ?
...
Let e be the element which was in the first position t
Boris Borcic wrote:
> does
>
> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>
> pick a random shuffle of x with uniform distribution ?
>
> Intuitively, assuming list.sort() does a minimal number of comparisons to
> achieve the sort, I'd say the answer is yes. But I don't feel quite
> confor
Boris Borcic wrote:
> does
>
> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>
> pick a random shuffle of x with uniform distribution ?
>
> Intuitively, assuming list.sort() does a minimal number of comparisons to
> achieve the sort, I'd say the answer is yes.
You would be mistaken (except
Boris Borcic wrote:
> does
>
> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>
> pick a random shuffle of x with uniform distribution ?
>
> Intuitively, assuming list.sort() does a minimal number of comparisons to
> achieve the sort, I'd say the answer is yes. But I don't feel quite
> confo
Boris Borcic <[EMAIL PROTECTED]> writes:
> To be more convincing... assume the algorithm is optimal and calls
That assumption is not even slightly realistic. Real-world sorting
algorithms almost never do a precisely minimal amount of comparison.
--
http://mail.python.org/mailman/listinfo/python-
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
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
Thanks for these details. BB
Tim Peters wrote:
> [ Boris Borcic]
>> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>>
>> pick a random shuffle of x with uniform distribution ?
>
> Say len(x) == N. With Python's current sort, the conjecture is true
> if and only if N <= 2.
>
>> Intuitively,
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
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 <
[ Boris Borcic]
> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>
> pick a random shuffle of x with uniform distribution ?
Say len(x) == N. With Python's current sort, the conjecture is true
if and only if N <= 2.
> Intuitively, assuming list.sort() does a minimal number of comparisons to
Dustan wrote:
> Boris Borcic wrote:
> > does
> >
> > x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
> >
> > pick a random shuffle of x with uniform distribution ?
> >
> > Intuitively, assuming list.sort() does a minimal number of comparisons to
> > achieve the sort, I'd say the answer is yes.
Boris Borcic wrote:
> does
>
> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>
> pick a random shuffle of x with uniform distribution ?
>
> Intuitively, assuming list.sort() does a minimal number of comparisons to
> achieve the sort, I'd say the answer is yes. But I don't feel quite
> confo
Boris Borcic wrote:
> does
>
> x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
>
> pick a random shuffle of x with uniform distribution ?
>
> Intuitively, assuming list.sort() does a minimal number of comparisons to
> achieve the sort, I'd say the answer is yes. But I don't feel quite
> con
does
x.sort(cmp = lambda x,y : cmp(random.random(),0.5))
pick a random shuffle of x with uniform distribution ?
Intuitively, assuming list.sort() does a minimal number of comparisons to
achieve the sort, I'd say the answer is yes. But I don't feel quite confortable
with the intuition... can an
20 matches
Mail list logo
