Velocity Reviews > Re: How to arrange some numbers

# Re: How to arrange some numbers

Tim Rentsch
Guest
Posts: n/a

 03-23-2013
Robert Wessel <(E-Mail Removed)> writes:

> On Sat, 23 Mar 2013 08:56:33 -0500, pete <(E-Mail Removed)>
> wrote:
>
>>Robert Wessel wrote:
>>
>>> Quicksort has all sorts of potential
>>> little gotchas, and you can't actually avoid them all even in a very
>>> competently implemented sort.

>>
>>One way to avoid quadratic behavior in quicksort,
>>is to sort the first half of the array first
>>and to then use the median value from that,
>>as the pivot to sort the second half.
>>
>>One example of that, is called "leapfrog sample sort".
>>
>>
>>

> (...code snipped...)
>
> That does not prevent worst case quadratic behavior any more than the
> median-of-three algorithm does. [snip unrelated]

Do you have any evidence or supporting arguments to back up this
claim? My calculations show it has a worst-case behavior which
is O( n ** 1.51 ) approximately, not quadratic.

Eric Sosman
Guest
Posts: n/a

 03-23-2013
On 3/23/2013 5:30 PM, Tim Rentsch wrote:
> Eric Sosman <(E-Mail Removed)> writes:
>
>> On 3/23/2013 9:56 AM, pete wrote:
>>> Robert Wessel wrote:
>>>
>>>> Quicksort has all sorts of potential
>>>> little gotchas, and you can't actually avoid them all even in a very
>>>> competently implemented sort.
>>>
>>> One way to avoid quadratic behavior in quicksort,
>>> is to sort the first half of the array first
>>> and to then use the median value from that,
>>> as the pivot to sort the second half.
>>> [...]

>>
>> If the array is already sorted (or anti-sorted), this
>> doesn't so much "avoid" quadratic behavior as "guarantee" it.

>
> I believe this conclusion is incorrect. According to
> my calculations, the worst case asymptotic behavior of
> this sorting method is O( n ** 1.51+ ), not quadratic.

It's possible we're interpreting the brief description
differently. My (mis?)understanding suggests that for a
sorted array of distinct keys

- The median key of the first half will be less than
every key of the second.

- Using that key in the first partitioning pass over
the second half will make no progress (the entire
second half lands in the "greater than" side of
the divide).

.... but perhaps you've analyzed a different algorithm.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d

Tim Rentsch
Guest
Posts: n/a

 03-23-2013
Eric Sosman <(E-Mail Removed)> writes:

> On 3/23/2013 5:30 PM, Tim Rentsch wrote:
>> Eric Sosman <(E-Mail Removed)> writes:
>>
>>> On 3/23/2013 9:56 AM, pete wrote:
>>>> Robert Wessel wrote:
>>>>
>>>>> Quicksort has all sorts of potential
>>>>> little gotchas, and you can't actually avoid them all even in a very
>>>>> competently implemented sort.
>>>>
>>>> One way to avoid quadratic behavior in quicksort,
>>>> is to sort the first half of the array first
>>>> and to then use the median value from that,
>>>> as the pivot to sort the second half.
>>>> [...]
>>>
>>> If the array is already sorted (or anti-sorted), this
>>> doesn't so much "avoid" quadratic behavior as "guarantee" it.

>>
>> I believe this conclusion is incorrect. According to
>> my calculations, the worst case asymptotic behavior of
>> this sorting method is O( n ** 1.51+ ), not quadratic.

>
> It's possible we're interpreting the brief description
> differently. My (mis?)understanding suggests that for a
> sorted array of distinct keys
>
> - The median key of the first half will be less than
> every key of the second.
>
> - Using that key in the first partitioning pass over
> the second half will make no progress (the entire
> second half lands in the "greater than" side of
> the divide).
>
> ... but perhaps you've analyzed a different algorithm.

Yes, that's what I thought you meant, and that was the starting
point of my calculations. The question then becomes what do you
assume for the recursion step? I assumed:

A. no further work on the first 25% of the array,
because it is sorted, and known to be less than
every other element of the array; and

B. full recursion on the other 75% of the array,
"forgetting" everything that was learned about
the 25% that is greater than the midpoint of
the first half, and already sorted, but which
potentially might intermix with the second half.

The combination of these gives the n ** 1.51+ result I mentioned.
(I'm not sure the "B" assumption matches the algorithm, but I
don't think it can be worse than what the algorithm actually
does.)

I did look at the cited document rather than relying on just the
posted description, but I confess I did not look closely at the
details of how the algorithm works. What I did see in the paper
makes me think my calculations are at least conservatively right
(ie, they give an upper bound, but maybe not a very good upper
bound), but I don't know that for sure because the details are
not explained well enough for me to understand easily.

Eric Sosman
Guest
Posts: n/a

 03-24-2013
On 3/23/2013 7:13 PM, Tim Rentsch wrote:
> Eric Sosman <(E-Mail Removed)> writes:
>
>> On 3/23/2013 5:30 PM, Tim Rentsch wrote:
>>> Eric Sosman <(E-Mail Removed)> writes:
>>>
>>>> On 3/23/2013 9:56 AM, pete wrote:
>>>>> Robert Wessel wrote:
>>>>>
>>>>>> Quicksort has all sorts of potential
>>>>>> little gotchas, and you can't actually avoid them all even in a very
>>>>>> competently implemented sort.
>>>>>
>>>>> One way to avoid quadratic behavior in quicksort,
>>>>> is to sort the first half of the array first
>>>>> and to then use the median value from that,
>>>>> as the pivot to sort the second half.
>>>>> [...]
>>>>
>>>> If the array is already sorted (or anti-sorted), this
>>>> doesn't so much "avoid" quadratic behavior as "guarantee" it.
>>>
>>> I believe this conclusion is incorrect. According to
>>> my calculations, the worst case asymptotic behavior of
>>> this sorting method is O( n ** 1.51+ ), not quadratic.

>>
>> It's possible we're interpreting the brief description
>> differently. My (mis?)understanding suggests that for a
>> sorted array of distinct keys
>>
>> - The median key of the first half will be less than
>> every key of the second.
>>
>> - Using that key in the first partitioning pass over
>> the second half will make no progress (the entire
>> second half lands in the "greater than" side of
>> the divide).
>>
>> ... but perhaps you've analyzed a different algorithm.

>
> Yes, that's what I thought you meant, and that was the starting
> point of my calculations. The question then becomes what do you
> assume for the recursion step? I assumed:
>
> A. no further work on the first 25% of the array,
> because it is sorted, and known to be less than
> every other element of the array; and

Hmmm. This is the point I'd question: How does one discover
that the first 1/4 is sorted, other than by sorting it? And if
it's sorted by the same "partition high by median of low" method,
it in turn got no benefit from its own sub-partitioning: The median
of the first 1/8 is below all of the other 1/8, and using it as
the partitioning element gives no benefit.

> B. full recursion on the other 75% of the array,
> "forgetting" everything that was learned about
> the 25% that is greater than the midpoint of
> the first half, and already sorted, but which
> potentially might intermix with the second half.
>
> The combination of these gives the n ** 1.51+ result I mentioned.
> (I'm not sure the "B" assumption matches the algorithm, but I
> don't think it can be worse than what the algorithm actually
> does.)

I'm still not sure how you combined things, but I'll trust
your analysis -- for the circumstances you've seen proper, which
may not be the same I'm assuming.

> I did look at the cited document rather than relying on just the
> posted description, but I confess I did not look closely at the
> details of how the algorithm works. What I did see in the paper
> makes me think my calculations are at least conservatively right
> (ie, they give an upper bound, but maybe not a very good upper
> bound), but I don't know that for sure because the details are
> not explained well enough for me to understand easily.

I confess to a "lazy attitude" (TAOCP 5.2, point F), in that I
find it? Yes! <http://www.cs.dartmouth.edu/~doug/mdmspe.pdf>)
tells me that no claim to completely eliminate Quicksort's quadratic
behavior is tenable, so I tossed the offered link into the same bag
with the perpetual motion machines. There may (or may not) be
something worthwhile there, and it may "often" avoid quadratic
behavior, but claiming that it "avoids" quadratic behavior violates
the, um, the Umpteenth Law of Thermodynamics, or something like that.

--
Eric Sosman
(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 03-24-2013
On 3/23/2013 11:09 PM, pete wrote:
> Eric Sosman wrote:
>
>> <http://www.cs.dartmouth.edu/~doug/mdmspe.pdf>)
>> tells me that no claim to completely eliminate Quicksort's quadratic
>> behavior is tenable

>
> That's not what it says.
> The very mild and realistic assumption that phase 1
> uses O(1) comparisons, does not apply to leapfrog sample sort.
>
> "The generalmethod works against any implementation of quicksort
> –even a randomizing one
> –that satisfies certain very mild and realistic assumptions."
>
> "1. Pick a data item as pivot.
> We assume that this phase uses O(1) comparisons."

Okay, I've broken down and followed the link. It looks like
a sheaf of presentation slides, which are a little hard to follow
lacking the speaker's contribution. Also, the algorithm is shown
in a sketchy sort of pseudocode; I imagine the speaker filled in
the missing details when presenting the results of the work.

Still, the diagram on Page 8 supports my original claim: On
a sorted array, using the median of the first half to partition
the second half is useless. The diagram illustrates at least
two optimistic assumptions:

1) The median of the first half is (close to) the median of
the entire array -- this is false if the array is sorted
or anti-sorted.

2) The median of the first half is also (close to) the median
of the second half -- false if the array is (anti-)sorted.

Also, note that the analysis starting on Page 11 is about the
"expected" performance, not the worst-case performance. The
Conclusion (page 21) states

"Thus, our result is the new lower bound for sorting
in terms of the *average* [emphasis mine] number of
comparisons."

The slides make no attempt to show that the worst-case behavior
is similar to the average -- perhaps the speaker notes, if we
fact that no such assertion is made is, I think, evidence that no
such claim is supportable: If somebody came up with a Quicksort
variant whose worst case was sub-quadratic, that fact would not
be buried in the speaker notes but would be right there in the
title of the paper. In red ink. Blinking red ink, with sound
effects and dancing girls.)

--
Eric Sosman
(E-Mail Removed)d

Tim Rentsch
Guest
Posts: n/a

 03-24-2013
Eric Sosman <(E-Mail Removed)> writes:

> On 3/23/2013 7:13 PM, Tim Rentsch wrote:
>> Eric Sosman <(E-Mail Removed)> writes:
>>
>>> On 3/23/2013 5:30 PM, Tim Rentsch wrote:
>>>> Eric Sosman <(E-Mail Removed)> writes:
>>>>
>>>>> On 3/23/2013 9:56 AM, pete wrote:
>>>>>> Robert Wessel wrote:
>>>>>>
>>>>>>> Quicksort has all sorts of potential
>>>>>>> little gotchas, and you can't actually avoid them all even in a very
>>>>>>> competently implemented sort.
>>>>>>
>>>>>> One way to avoid quadratic behavior in quicksort,
>>>>>> is to sort the first half of the array first
>>>>>> and to then use the median value from that,
>>>>>> as the pivot to sort the second half.
>>>>>> [...]
>>>>>
>>>>> If the array is already sorted (or anti-sorted), this
>>>>> doesn't so much "avoid" quadratic behavior as "guarantee" it.
>>>>
>>>> I believe this conclusion is incorrect. According to
>>>> my calculations, the worst case asymptotic behavior of
>>>> this sorting method is O( n ** 1.51+ ), not quadratic.
>>>
>>> It's possible we're interpreting the brief description
>>> differently. My (mis?)understanding suggests that for a
>>> sorted array of distinct keys
>>>
>>> - The median key of the first half will be less than
>>> every key of the second.
>>>
>>> - Using that key in the first partitioning pass over
>>> the second half will make no progress (the entire
>>> second half lands in the "greater than" side of
>>> the divide).
>>>
>>> ... but perhaps you've analyzed a different algorithm.

>>
>> Yes, that's what I thought you meant, and that was the starting
>> point of my calculations. The question then becomes what do you
>> assume for the recursion step? I assumed:
>>
>> A. no further work on the first 25% of the array,
>> because it is sorted, and known to be less than
>> every other element of the array; and

>
> Hmmm. This is the point I'd question: How does one discover
> that the first 1/4 is sorted, other than by sorting it?

It is sorted, recursively, by the same method; I think the
algorithm is pretty clear about that. In any case the cost
of that recursive sub-sort is included in my accounting.

> And if
> it's sorted by the same "partition high by median of low" method,
> it in turn got no benefit from its own sub-partitioning: The median
> of the first 1/8 is below all of the other 1/8, and using it as
> the partitioning element gives no benefit.

Here is where I think your mistake is. If we recursively sort a
sub-array half the size, and then after only O(n) more work we no
longer have to deal with 25% of the whole array (or any fixed
fraction, but the exponent gets larger as the fraction gets
smaller), the sort routine as a whole is decidedly sub-quadratic.
Looking recursively at half the array gives quadratic behavior
only if the part that is finished being sorted asymptotically
goes to zero as a fraction of the whole array; if that part is
always greater than some fixed percentage, the performance is
better than quadratic. Or to say it another way, there may be
little progress, but there is not no progress; as the fraction
goes down the exponent of n goes up, but it never gets to 2
unless the fraction goes to zero in the limit.

>> B. full recursion on the other 75% of the array,
>> "forgetting" everything that was learned about
>> the 25% that is greater than the midpoint of
>> the first half, and already sorted, but which
>> potentially might intermix with the second half.
>>
>> The combination of these gives the n ** 1.51+ result I mentioned.
>> (I'm not sure the "B" assumption matches the algorithm, but I
>> don't think it can be worse than what the algorithm actually
>> does.)

>
> I'm still not sure how you combined things, but I'll trust
> your analysis -- for the circumstances you've seen proper, which
> may not be the same I'm assuming.

My intention was to make the same assumptions that you were. I
believe that is actually right, but let me state them explicitly:

1. Half the array is sorted recursively using the same
algorithm (with appropriate cutoff for very small
number of elements);

2. After (1), a scan requiring O(n) work is done, which
discovers that every element in the non-sorted half
is larger than the median of the sorted half;

3. The lower quarter is now known to be sorted, and in the
right final destination, and nothing more need be done
with it (if the array is reverse-sorted that may change
the constant factor but doesn't change the power of n);
and

4. The remaining sorted quarter and unsorted upper half
need to be dealt with together, which is done by a
recursive call to the same routine. (I now believe
that doesn't match the algorithm, but that was my
assumption for the earlier calculations.)

Those four together lead to the O( n ** 1.51+ ) assessment.
That's an empirical conclusion, but I'm confident actual
analysis would bear it out (ie, as approximately right).

>> I did look at the cited document rather than relying on just the
>> posted description, but I confess I did not look closely at the
>> details of how the algorithm works. What I did see in the paper
>> makes me think my calculations are at least conservatively right
>> (ie, they give an upper bound, but maybe not a very good upper
>> bound), but I don't know that for sure because the details are
>> not explained well enough for me to understand easily.

>
> I confess to a "lazy attitude" (TAOCP 5.2, point F), in that I
> find it? Yes! <http://www.cs.dartmouth.edu/~doug/mdmspe.pdf>)
> tells me that no claim to completely eliminate Quicksort's quadratic
> behavior is tenable, so I tossed the offered link into the same bag
> with the perpetual motion machines. There may (or may not) be
> something worthwhile there, and it may "often" avoid quadratic
> behavior, but claiming that it "avoids" quadratic behavior violates
> the, um, the Umpteenth Law of Thermodynamics, or something like that.

I went back at looked at the paper more closely, and now I think
I understand what the algorithm is doing. Based on my current
understanding, the algorithm is actually quite good. In fact,
for arrays that are initially sorted or reverse-sorted, it gives
linear performance -- not O(N log N), but O(N). So it looks
pretty cool. And I believe it does guarantee non-quadratic
behavior, in all cases.

Tim Rentsch
Guest
Posts: n/a

 03-24-2013
pete <(E-Mail Removed)> writes:

> Tim Rentsch wrote:
>>
>> Robert Wessel <(E-Mail Removed)> writes:
>>
>> > On Sat, 23 Mar 2013 08:56:33 -0500, pete <(E-Mail Removed)>
>> > wrote:
>> >
>> >>Robert Wessel wrote:
>> >>
>> >>> Quicksort has all sorts of potential
>> >>> little gotchas, and you can't actually avoid them all even in a very
>> >>> competently implemented sort.
>> >>
>> >>One way to avoid quadratic behavior in quicksort,
>> >>is to sort the first half of the array first
>> >>and to then use the median value from that,
>> >>as the pivot to sort the second half.
>> >>
>> >>One example of that, is called "leapfrog sample sort".
>> >>
>> >>
>> >>
>> > (...code snipped...)
>> >
>> > That does not prevent worst case quadratic behavior
>> > any more than the
>> > median-of-three algorithm does. [snip unrelated]

>>
>> Do you have any evidence or supporting arguments to back up this
>> claim? My calculations show it has a worst-case behavior which
>> is O( n ** 1.51 ) approximately, not quadratic.

>
> According to Albacea,
>
> "In this paper, we present a practical Quicksort-based
> sorting algorithm that exhibits the following properties:
> (1) O(n(log n) 2) worst case;"

Strictly speaking that does not invalidate my statement, since
big-Oh notation is only an upper bound, and not necessarily a
tight upper bound.

I added a smiley there, but in fact when I wrote the earlier
comments I knew the bound I was giving might not be a really good
upper bound, only that it was an upper bound. I made some
assumptions (conservative, I thought, and that turned out to
be right) about what the algorithm did, and those assumptions
led to this performance behavior, but it isn't how the algorithm
actually works.

Now that I have gone back and looked at the paper in more detail,
I think it's a very clever algorithm. I haven't actually done
the analysis myself to back this up (and I haven't yet looked
the link you posted - thank you for that!), but it does look
like an O(N log N) kind of algorithm. Very cool.

Tim Rentsch
Guest
Posts: n/a

 03-24-2013
pete <(E-Mail Removed)> writes:

> According to Albacea,
>
> "In this paper, we present a practical Quicksort-based
> sorting algorithm that exhibits the following properties:
> (1) O(n(log n) 2) worst case;"

I see, that actually is O( n * (log n)**2 ) worse-case performance,
not O( n * log n ). Still, not too shabby.

Eric Sosman
Guest
Posts: n/a

 03-24-2013
On 3/23/2013 11:52 PM, pete wrote:
> Eric Sosman wrote:
>>
>> On 3/23/2013 5:30 PM, Tim Rentsch wrote:
>>> Eric Sosman <(E-Mail Removed)> writes:
>>>
>>>> On 3/23/2013 9:56 AM, pete wrote:
>>>>> Robert Wessel wrote:
>>>>>
>>>>>> Quicksort has all sorts of potential
>>>>>> little gotchas, and you can't actually avoid them all even in a very
>>>>>> competently implemented sort.
>>>>>
>>>>> One way to avoid quadratic behavior in quicksort,
>>>>> is to sort the first half of the array first
>>>>> and to then use the median value from that,
>>>>> as the pivot to sort the second half.
>>>>> [...]
>>>>
>>>> If the array is already sorted (or anti-sorted), this
>>>> doesn't so much "avoid" quadratic behavior as "guarantee" it.
>>>
>>> I believe this conclusion is incorrect. According to
>>> my calculations, the worst case asymptotic behavior of
>>> this sorting method is O( n ** 1.51+ ), not quadratic.

>>
>> It's possible we're interpreting the brief description
>> differently. My (mis?)understanding suggests that for a
>> sorted array of distinct keys
>>
>> - The median key of the first half will be less than
>> every key of the second.
>>
>> - Using that key in the first partitioning pass over
>> the second half will make no progress (the entire
>> second half lands in the "greater than" side of
>> the divide).
>>
>> ... but perhaps you've analyzed a different algorithm.

>
> To sort an array,
>
> 1 Sort the first half of the array.
>
> 2 Use the median value of the sorted first half,
> as the pivot value for sorting the second half.
>
> Then
> what you have in the first half of the array is:
> (a) an ordered partition of elements
> less than or equal to the pivot
> (b) the pivot
> (c) an ordered partition of elements
> greater than or equal to the pivot
> What you have in the second half of the array is:
> (d) a disordered partition of elements
> less than or equal to the pivot
> (e) a disordered partition of elements
> greater than or equal to the pivot

Fine. If the array was sorted to begin with, (d) is empty
and (e) is the entire second half.

> The next steps which I had previously omitted, are:
>
> 4 Group (b) and (c) together and swap them with (d)
> to get the parts of the array into this order:

Since (d) is empty, this is a no-op. A no-op does not
advance the state of the computation.

> (a) an ordered partition of elements
> less than or equal to the pivot
> (d) a disordered partition of elements
> less than or equal to the pivot

The degree of disorder in an empty partition is equal to
the number of angels that dance on the ATM keypad while I try
to enter my PIN, all of them clapping one hand in a forest
where nobody is listening.

> (b) the pivot
> (c) an ordered partition of elements
> greater than or equal to the pivot
> (e) a disordered partition of elements
> greater than or equal to the pivot

Yes. And (e) is the entire second half or the original
sorted array.

> Then the pivot has been sorted.
>
> 5 Sort the partions before and after the pivot.
> Use the median of (a) as a new pivot value used to sort (d).

Okay: (d) is empty, so that's easy.

> Use the median of (c) as a new pivot value used to sort (e).

Okay: Since everything in (c) is less than everything in (e),
then in particular the median of (c) is less than everything in
(e) and this step, too, makes no advance.

> If (a) has less elements than (d),
> then you should be able to figure what to do.
> Likewise for (c) and (e).

Not sure what you're getting at here; not sure it matters.

Concrete example: Let's sort the numbers 1 through 10. We
begin by sorting the first five (doesn't matter how), obtaining
1-2-3-4-5. Your (a) is 1-2, (b) is 3, (c) is 4-5, (d) is empty,
and (e) is 6-7-8-9-10. Swapping (b+c) with (d) makes no change,
and you now have (a=1-2),(b=3),(d=empty),(c=4-5),(e=6-7-8-9-10).
Now you use the median of (c) -- which might be 4, or 4.5, or 5 --
to partition (e), and again nothing happens. The algorithm has
split a problem of size 10 into two sub-problems of size 5, solved
one of them (we don't care how), and then split the second into
sub-sub-problems -- of sizes 0 and, er, 5.

--
Eric Sosman
(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 03-24-2013
On 3/23/2013 11:20 PM, pete wrote:
>[...]
> According to Albacea,
>
> "In this paper, we present a practical Quicksort-based
> sorting algorithm that exhibits the following properties:
> (1) O(n(log n) 2) worst case;"

They'll let you read beyond the abstract for a mere \$29.95.

--
Eric Sosman
(E-Mail Removed)d