Velocity Reviews > Re: How to arrange some numbers

Re: How to arrange some numbers

Eric Sosman
Guest
Posts: n/a

 03-24-2013
On 3/23/2013 11:46 PM, Eric Sosman wrote:
> 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:
>>>>>> [...]
>>>>>> 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.
>>>> [...]
>>> [...]

>> [...]

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

.... which doesn't so much "support" my claim as "demolish" it.
The method sorts the first half of the array with what we may
as well call C(n/2) comparisons, then makes n/2 comparisons in
the useless partitioning pass, then sorts the second half in
another C(n/2) comparisons. So

C(n) = 2*C(n/2) + n/2
= 2*(2*C(n/4) + n/4) + n/2
= 2*(2*(C(n/ + n/ + n/4) + n/2
= ... (assume n a power of 2 for simplicity) ...
= n*C(1) + lg(n)*n/2
= n*lg(n) - n

.... so the entire sort uses O(n*log(n)) comparisons, not O(n*n).

Now, if you'll excuse me, I've got to go wash this thick
encrustation of egg off my face.

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

Öö Tiib
Guest
Posts: n/a

 03-24-2013
On Saturday, 23 March 2013 23:23:07 UTC+2, Tim Rentsch wrote:
> Tiib writes:
> > I am merely implying such things:
> >
> > * merge sort algorithm was invented 1945, Quicksort 1960, Heapsort bit
> > more recently. On each case those were implemented too.
> > * we do not need to erase existing well-tested implementations to write
> > new ones.
> > * we often do use existing well-tested implementations to compare
> > the performance and correctness with the new implementations or algorithms.

>
> This is a silly argument. Obviously there were no implementations
> in C of _any_ sorting algorithm in 1960, let alone 1945. When
> working in a more recently developed language, usually it is
> necessary to re-implement some algorithms that were implemented
> previously in other languages.

There were 3 things I implied as widely known. None of those is silly,
these are bare-bone facts. I apparently have to add one more for
people with astonishing imagination ...
* it has not been hard to integrate C with other languages.

> If you really can't imagine any set of circumstances in which it
> might be more cost effective to write a sort routine yourself rather
> than spending time to find and use an existing one, you have very
> limited powers of imagination.

Why not to demonstrate your unlimited imagination and to bring
reasonable example?

Rosario1903
Guest
Posts: n/a

 03-25-2013
On 20 Mar 2013 05:53:07 GMT, (E-Mail Removed)
<(E-Mail Removed)> wrote:

>In article <(E-Mail Removed)>,
>Rosario1903 <(E-Mail Removed)> wrote:
>> On Sun, 17 Mar 2013 07:22:38 -0500, pete <(E-Mail Removed)>
>> wrote:
>>
>>
>> >I don't really know anything about parallel systems.

>>
>> qsort is parallelizable...
>> divide the interval
>> assign the 2 interval to 2 different cpu for doing ordering
>> i think could be O(N) in one multi cpu sys
>>

>

yes i too
if in the cpu there are n processors, and qsort is parallelizable
i think could be O(N/n) because each cpu make its job in parallel

gwowen
Guest
Posts: n/a

 03-26-2013
On Mar 22, 8:37*am, James Dow Allen <(E-Mail Removed)> wrote:

> 1. My favorite solution is xkcd's as provided by Mark Bluemel.
> 2. I'm not sure England's English is still the standard English.
> After all, Englishmen's passports don't even
> have the word "England" on them anymore.

Have they ever? (excluding when they were hand-written and signed by
the sovereign)

Martin Shobe
Guest
Posts: n/a

 03-26-2013
On 3/15/2013 5:55 PM, BartC wrote:
>
> I've provided some code below. Note that this uses the world's worst sort
> method, so won't get you many marks. But it's also my favourite sort.
>

Worst sorting method? I'll admit that better ones have been devised, but
even for deterministic sorts, it's got nothing on a permutation sort
that checks every pair of elements to see if the list is sorted. That's
at least an O(n!n**2) algorithm.

Martin Shobe

blmblm@myrealbox.com
Guest
Posts: n/a

 03-27-2013
In article <(E-Mail Removed)>,
Rosario1903 <(E-Mail Removed)> wrote:
> On 20 Mar 2013 05:53:07 GMT, (E-Mail Removed)
> <(E-Mail Removed)> wrote:
>
> >In article <(E-Mail Removed)>,
> >Rosario1903 <(E-Mail Removed)> wrote:
> >> On Sun, 17 Mar 2013 07:22:38 -0500, pete <(E-Mail Removed)>
> >> wrote:
> >>
> >>
> >> >I don't really know anything about parallel systems.
> >>
> >> qsort is parallelizable...
> >> divide the interval
> >> assign the 2 interval to 2 different cpu for doing ordering
> >> i think could be O(N) in one multi cpu sys
> >>

> >

>
> yes i too
> if in the cpu there are n processors, and qsort is parallelizable
> i think could be O(N/n) because each cpu make its job in parallel

But .... If that were possible, with n=1 you'd have an O(N) sort,
and isn't there a theoretical result that the best (comparison-based)
sort is O(N log N) ?

--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.

Nobody
Guest
Posts: n/a

 03-28-2013
On Wed, 27 Mar 2013 07:44:42 -0500, Robert Wessel wrote:

> In any event there are parallel sorting algorithms (Quicksort appears easy
> to parallelize, but it really doesn't work all that well in that context,
> since the sizes of the work units varies too much), although none are
> particularly efficient in how much work they do, they can nonetheless
> complete a sort in less than lg(N!) time (but while doing considerably
> *more* than lg(N!) work).

Sorting networks (static sorts) are typical for SIMD-based parallelism
(e.g. GPUs), as the choice of items to compare-and-swap doesn't depend
upon the data.

Practical algorithms invariably have O(n.log^2(n)) operations, consisting
of O(log^2(n)) depth and O(n) width, readily-parallelisable over the width.

Popular choices are bitonic mergesort and even-odd mergesort.

Rosario1903
Guest
Posts: n/a

 03-29-2013
On 27 Mar 2013 11:15:52 GMT, <blmblm> wrote:

>In article <(E-Mail Removed)>,
>Rosario1903 <(E-Mail Removed)> wrote:
>> On 20 Mar 2013 05:53:07 GMT,
>> <blmblm> wrote:
>>
>> >In article <(E-Mail Removed)>,
>> >Rosario1903 <(E-Mail Removed)> wrote:
>> >> On Sun, 17 Mar 2013 07:22:38 -0500, pete <(E-Mail Removed)>
>> >> wrote:
>> >>
>> >>
>> >> >I don't really know anything about parallel systems.
>> >>
>> >> qsort is parallelizable...
>> >> divide the interval
>> >> assign the 2 interval to 2 different cpu for doing ordering
>> >> i think could be O(N) in one multi cpu sys
>> >>
>> >

>>
>> yes i too
>> if in the cpu there are n processors, and qsort is parallelizable
>> i think could be O(N/n) because each cpu make its job in parallel

>
>But .... If that were possible, with n=1 you'd have an O(N) sort,
>and isn't there a theoretical result that the best (comparison-based)
>sort is O(N log N) ?

yes
the qsort algo would be O((N log N))
even in a multicore cpu because O say nothing of the time the
operation is done, in the few i remember is connect to the number of
operation that in a multicore cpu would be > than in 1cpu

but if the qsort algo would be parallelizable and there is one multi n
core cpu
the time could be: Time( (N log N) / n)
instead of the time in one cpu Time(N log N)

blmblm@myrealbox.com
Guest
Posts: n/a

 03-29-2013
In article <(E-Mail Removed)>,
Robert Wessel <(E-Mail Removed)> wrote:
> On 27 Mar 2013 11:15:52 GMT, (E-Mail Removed)
> <(E-Mail Removed)> wrote:
>
> >In article <(E-Mail Removed)>,
> >Rosario1903 <(E-Mail Removed)> wrote:
> >> On 20 Mar 2013 05:53:07 GMT, (E-Mail Removed)
> >> <(E-Mail Removed)> wrote:
> >>
> >> >In article <(E-Mail Removed)>,
> >> >Rosario1903 <(E-Mail Removed)> wrote:
> >> >> On Sun, 17 Mar 2013 07:22:38 -0500, pete <(E-Mail Removed)>
> >> >> wrote:
> >> >>
> >> >>
> >> >> >I don't really know anything about parallel systems.
> >> >>
> >> >> qsort is parallelizable...
> >> >> divide the interval
> >> >> assign the 2 interval to 2 different cpu for doing ordering
> >> >> i think could be O(N) in one multi cpu sys
> >> >>
> >> >
> >> >I'm skeptical (about O(N)),
> >>
> >> yes i too
> >> if in the cpu there are n processors, and qsort is parallelizable
> >> i think could be O(N/n) because each cpu make its job in parallel

> >
> >But .... If that were possible, with n=1 you'd have an O(N) sort,
> >and isn't there a theoretical result that the best (comparison-based)
> >sort is O(N log N) ?

>
>
> Ignoring duplicate keys, a sort is the selection of a particular
> permutation of the input data. As there are N! possible permutations,
> the sort is the selection of one of those. Identifying N! items
> requires lg(N!) bits (base 2 log) of information, so any sort must
> produce lg(N!) bits of information.
>
> A sort that produces only a single bit of information per basic
> operation (such as a comparison), will have to perform lg(N!) of those
> basic operations. Some sorts can, under the correct circumstances,
> produce more than one bit of information per operation (the various
> address computing sorts and radix sorts, for example), and thus can
> sort with fewer than lg(N!) operations (but they still have to produce
> lg(N!) bits of information).
>
> Since (N*lg(N)) happens to be a (slightly high) approximation for
> lg(N!) (see Stirling's Approximation), we usually say that n*log(n) is
> the lower bounds for sorting for methods producing only one bit of
> information per operation.

Good heavens! My casual reference to the theoretical result wasn't
actually intended to result in someone explaining/summarizing it,
but .... Thanks; very interesting!

> But that's the amount of *work* you have to do, it says nothing about
> how well that work might parallelize, or how long that might all take.
>
> In any event there are parallel sorting algorithms (Quicksort appears
> easy to parallelize, but it really doesn't work all that well in that
> context, since the sizes of the work units varies too much), although
> none are particularly efficient in how much work they do, they can
> nonetheless complete a sort in less than lg(N!) time (but while doing
> considerably *more* than lg(N!) work).

--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.

blmblm@myrealbox.com
Guest
Posts: n/a

 03-29-2013
In article <(E-Mail Removed)>,
Rosario1903 <(E-Mail Removed)> wrote:
> On 27 Mar 2013 11:15:52 GMT, <blmblm> wrote:
>
> >In article <(E-Mail Removed)>,
> >Rosario1903 <(E-Mail Removed)> wrote:
> >> On 20 Mar 2013 05:53:07 GMT,
> >> <blmblm> wrote:
> >>
> >> >In article <(E-Mail Removed)>,
> >> >Rosario1903 <(E-Mail Removed)> wrote:
> >> >> On Sun, 17 Mar 2013 07:22:38 -0500, pete <(E-Mail Removed)>
> >> >> wrote:
> >> >>
> >> >>
> >> >> >I don't really know anything about parallel systems.
> >> >>
> >> >> qsort is parallelizable...
> >> >> divide the interval
> >> >> assign the 2 interval to 2 different cpu for doing ordering
> >> >> i think could be O(N) in one multi cpu sys
> >> >>
> >> >
> >> >I'm skeptical (about O(N)),
> >>
> >> yes i too
> >> if in the cpu there are n processors, and qsort is parallelizable
> >> i think could be O(N/n) because each cpu make its job in parallel

> >
> >But .... If that were possible, with n=1 you'd have an O(N) sort,
> >and isn't there a theoretical result that the best (comparison-based)
> >sort is O(N log N) ?

>
> yes
> the qsort algo would be O((N log N))
> even in a multicore cpu because O say nothing of the time the
> operation is done, in the few i remember is connect to the number of
> operation that in a multicore cpu would be > than in 1cpu

No offense meant[*], but I can't quite parse this; maybe someone
else can help?
[*] I have much respect for the even-partially-multilingual, having
never been able to even approach fluency in more than one language.

> but if the qsort algo would be parallelizable and there is one multi n
> core cpu
> the time could be: Time( (N log N) / n)
> instead of the time in one cpu Time(N log N)

It seems to me that O((N log N) / n) would be an upper bound on
the time needed to sort N elements with n processing elements.
I'm very skeptical that quicksort will come very close to this
bound, for reasons cited elsethread. Just sayin'. As has been
mentioned elsethread, other algorithms specifically designed to
exploit potential parallelism may do better, though possibly at a
cost of doing more total work.

--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.