Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #7506 > unrolled thread

Using Java Classes to Sort a Small Array Quickly

Back to article view | Back to comp.lang.java.programmer

Contents

  Using Java Classes to Sort a Small Array Quickly KevinSimonson <kvnsmnsn@hotmail.com> - 2011-08-31 19:48 -0700
    Re: Using Java Classes to Sort a Small Array Quickly markspace <-@.> - 2011-08-31 20:39 -0700
      Re: Using Java Classes to Sort a Small Array Quickly bugbear <bugbear@trim_papermule.co.uk_trim> - 2011-09-01 09:18 +0100
      Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:38 -0700
        Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-01 03:50 -0700
      Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-11 23:14 +0200
        Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-11 17:53 -0400
          Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-12 01:40 +0200
            Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-11 20:32 -0400
              Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 02:54 +0200
                Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-16 21:03 -0400
                  Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 16:52 +0200
                    Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-17 11:05 -0400
                      Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-18 15:41 +0200
                        Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-18 12:53 -0700
                          Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-18 13:20 -0700
            Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-11 21:10 -0400
              Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-11 20:30 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-12 19:13 -0400
                  Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-12 17:42 -0700
                    Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 02:54 +0200
                      Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-16 21:13 -0400
                      Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-16 23:14 -0700
                        Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 16:53 +0200
                  Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-12 21:24 -0400
            Re: Using Java Classes to Sort a Small Array Quickly Gene Wirchenko <genew@ocis.net> - 2011-09-12 10:57 -0700
              Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-12 19:01 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-12 21:29 -0400
                  Re: Using Java Classes to Sort a Small Array Quickly markspace <-@.> - 2011-09-12 19:49 -0700
                    Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-12 21:51 -0700
                    Re: Using Java Classes to Sort a Small Array Quickly Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-09-13 11:32 -0500
                    Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-13 21:51 -0400
                      Re: Using Java Classes to Sort a Small Array Quickly Gene Wirchenko <genew@ocis.net> - 2011-09-14 11:00 -0700
                  Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-13 06:33 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Gene Wirchenko <genew@ocis.net> - 2011-09-13 09:48 -0700
    Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 00:25 -0400
      Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 00:54 -0400
      Re: Using Java Classes to Sort a Small Array Quickly bugbear <bugbear@trim_papermule.co.uk_trim> - 2011-09-01 09:20 +0100
        Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 08:06 -0400
      Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:43 -0700
    Re: Using Java Classes to Sort a Small Array Quickly Robert Klemme <shortcutter@googlemail.com> - 2011-09-01 08:32 +0200
    Re: Using Java Classes to Sort a Small Array Quickly RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-09-01 10:08 +0100
      Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-01 04:02 -0700
    Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 02:37 -0700
    Re: Using Java Classes to Sort a Small Array Quickly Roedy Green <see_website@mindprod.com.invalid> - 2011-09-01 04:53 -0700
    Re: Using Java Classes to Sort a Small Array Quickly Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-09-01 09:05 -0500

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#8096

In article <900ffdda-7170-44e3-a141-bfec09c74dd1
@glegroupsg2000goo.googlegroups.com>, lewbloch@gmail.com says...
> 
> Arne Vajhøj wrote:
> > Lew wrote:
> > > Arne Vajhøj wrote:
> > >> Wanja Gayk wrote:
> > >>> esosman@ieee-dot-org.invalid says...
> > >>>> Wanja Gayk wrote:
> > >>>>> Here's the proof: Sorting an array of positive integers in O(n) time:
> > > ...
> > >>>>        Very nice!  Would you care to try this approach on a shorter
> > >>>> input array, like
> > >>>>
> > >>>> 	data = new int[] { Integer.MAX_VALUE };
> > >>>>
> > >>>> This case should be quite simple, since the array is already sorted.
> > >>>> Let us know how you make out, will you?
> > >>>
> > >>> I didn't say it works for any array out there, did I?
> > >
> > > By using big-O notation, you said something about the behavior of the algorithm as the size of the data set tends to infinity, so yes, you did.
> > >
> > >> No.
> > >>
> > >> But a solution is a bit more practical if it does.
> > >
> > > Wanja was making a joke.  The performance of an algorithm on one particular data set is irrelevant to a discussion of asymptotic performance.  The hub of the joke was his reference to "O(n)" and calling it "proof" when he was making no statement about asymptotic performance.
> > >
> > > I get it.
> > 
> > ????
> > 
> > Bucket sort is O(n) in n.
> 
> n+k in the average, n^2 worst-case, but that has nothing to do with the joke as I read it.  It looked like he was talking about one specific array, and then he challenged us with "I didn't say it works for any array out there, did I?"
> 
> It looks like I did misread his post.  I didn't realize he was speaking of the general case given the presence of only one input.

The claim was that _any_ sort would be at least O(n log n). I've proven 
him wrong by sorting something in o(n) using a kind of bucket sort, that 
trades number range for runtime complexity. 
Mind you that I expected O(n) as being used as a general description of 
the complexity, not as upper bound. Yes, I was making a joke there, but 
there is a serious side to it:
Since the number range is limited to the maximum number of buckets and 
the size of the sequence is limited to the maximum capacity of a bucket, 
this is no general sort. But a specialized sort like that is not 
impractical at all, it's just of limited use. Say you've got a list of 
some ten thousands of books that need to be sorted by their price or 
number of pages whatsoever, then you'd have a pretty limited range of 
numbers (buckets). So given enough memory you could sort them very, very 
fast and if it's just for finding the median. If that's what you have to 
do very, very often it may be worth considering.
Linked Lists are also of limited use, so what? There are particular use 
cases where they can be the best data structure for the job.

Kind regards,
Wanja


-- 
..Alesi's problem was that the back of the car was jumping up and down 
dangerously - and I can assure you from having been teammate to 
Jean Alesi and knowing what kind of cars that he can pull up with, 
when Jean Alesi says that a car is dangerous - it is. [Jonathan Palmer]

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

[toc] | [prev] | [next] | [standalone]

#8099

On 9/16/2011 8:54 PM, Wanja Gayk wrote:
> In article<900ffdda-7170-44e3-a141-bfec09c74dd1
> @glegroupsg2000goo.googlegroups.com>, lewbloch@gmail.com says...
>>
>> Arne Vajhøj wrote:
>>> Lew wrote:
>>>> Arne Vajhøj wrote:
>>>>> Wanja Gayk wrote:
>>>>>> esosman@ieee-dot-org.invalid says...
>>>>>>> Wanja Gayk wrote:
>>>>>>>> Here's the proof: Sorting an array of positive integers in O(n) time:
>>>> ...
>>>>>>>         Very nice!  Would you care to try this approach on a shorter
>>>>>>> input array, like
>>>>>>>
>>>>>>> 	data = new int[] { Integer.MAX_VALUE };
>>>>>>>
>>>>>>> This case should be quite simple, since the array is already sorted.
>>>>>>> Let us know how you make out, will you?
>>>>>>
>>>>>> I didn't say it works for any array out there, did I?
>>>>
>>>> By using big-O notation, you said something about the behavior of the algorithm as the size of the data set tends to infinity, so yes, you did.
>>>>
>>>>> No.
>>>>>
>>>>> But a solution is a bit more practical if it does.
>>>>
>>>> Wanja was making a joke.  The performance of an algorithm on one particular data set is irrelevant to a discussion of asymptotic performance.  The hub of the joke was his reference to "O(n)" and calling it "proof" when he was making no statement about asymptotic performance.
>>>>
>>>> I get it.
>>>
>>> ????
>>>
>>> Bucket sort is O(n) in n.
>>
>> n+k in the average, n^2 worst-case, but that has nothing to do with the joke as I read it.  It looked like he was talking about one specific array, and then he challenged us with "I didn't say it works for any array out there, did I?"
>>
>> It looks like I did misread his post.  I didn't realize he was speaking of the general case given the presence of only one input.
>
> The claim was that _any_ sort would be at least O(n log n). I've proven
> him wrong by sorting something in o(n) using a kind of bucket sort, that
> trades number range for runtime complexity.

     And for correctness.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#8101

On 9/16/2011 5:54 PM, Wanja Gayk wrote:
...
> The claim was that _any_ sort would be at least O(n log n). I've proven
> him wrong by sorting something in o(n) using a kind of bucket sort, that
> trades number range for runtime complexity.
...

Why not just go with radix sort? It seems like a better example of a
practical O(n) sort.

The proof of the \Omega(n log n) lower bound only applies to comparison
sorts, so there is nothing surprising about the existence of O(n) sorts.

Patricia

[toc] | [prev] | [next] | [standalone]

#8105

In article <baSdnU7u2r5Bp-nTnZ2dnUVZ_uqdnZ2d@earthlink.com>, 
pats@acm.org says...

> Why not just go with radix sort? It seems like a better example of a
> practical O(n) sort.
> 
> The proof of the \Omega(n log n) lower bound only applies to comparison
> sorts, so there is nothing surprising about the existence of O(n) sorts.

Yeah, why not go with radix sort? Whatever algorithm fits. 
This was the just first one that came to my mind.

Kind regards,
Wanja


-- 
..Alesi's problem was that the back of the car was jumping up and down 
dangerously - and I can assure you from having been teammate to 
Jean Alesi and knowing what kind of cars that he can pull up with, 
when Jean Alesi says that a car is dangerous - it is. [Jonathan Palmer]

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

[toc] | [prev] | [next] | [standalone]

#7942

On 9/12/2011 7:13 PM, Arne Vajhøj wrote:
> On 9/11/2011 11:30 PM, Lew wrote:
>> Arne Vajhøj wrote:
>>> Wanja Gayk wrote:
>>>> esosman@ieee-dot-org.invalid says...
>>>>> Wanja Gayk wrote:
>>>>>> Here's the proof: Sorting an array of positive integers in O(n) time:
>> ...
>>>>> Very nice! Would you care to try this approach on a shorter
>>>>> input array, like
>>>>>
>>>>> data = new int[] { Integer.MAX_VALUE };
>>>>>
>>>>> This case should be quite simple, since the array is already sorted.
>>>>> Let us know how you make out, will you?
>>>>
>>>> I didn't say it works for any array out there, did I?
>>
>> By using big-O notation, you said something about the behavior of the
>> algorithm as the size of the data set tends to infinity, so yes, you did.
>>
>>> No.
>>>
>>> But a solution is a bit more practical if it does.
>>
>> Wanja was making a joke. The performance of an algorithm on one
>> particular data set is irrelevant to a discussion of asymptotic
>> performance.

     What about correctness?  Try his code on the one-element array
I offered: I guarantee that performance will not be an issue.  (In
particular, I guarantee you will not get a correct result *and* you
will not run out of memory.)

> Bucket sort is O(n) in n.

     It depends on what you choose to count, and how.  Question: How
much time does it take to select between K alternatives?  You need
at least lg(K) decisions.  Even if those decisions are being made at
the level of individual transistors you need more time to coordinate
a thousand transistors than to coordinate three.  In hardware, this
shows up as a slower clock speed, and in other ways as well, so it
is an error to consider "time to decision" as a constant.

     Depending on how you choose to count.  Many things can be proven
if you select your counting schemes with due care ...

     There's a famous algorithm for finding the largest of an unlimited
quantity of positive numbers: You represent the numbers as chunks of
uncooked spaghetti, each of a length proportional to the number
represented.  That's your input.  Algorithm: Pick up the whole bunch,
turn it upright, plonk one end down on the kitchen counter, and pluck
out the tallest spaghetto (spaghettus?).  Voila! An O(1) maximum-
finding algorithm!

     Discerning the flaws in this method is left as an exercise for
the astute reader.

> Big O for execution speed traditionally does not look at
> memory restrictions and data type restrictions.

     Big O for proton density traditionally does not look at execution
time.  Big O for the error in Stirling's approximation traditionally
does not look at proton density.  Big O for X traditionally does not
look at Y.  So?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#7908

On Mon, 12 Sep 2011 01:40:50 +0200, Wanja Gayk <brixomatic@yahoo.com>
wrote:

>In article <j4jala$dkh$1@dont-email.me>, esosman@ieee-dot-org.invalid 
>says...
>
>>      Very nice!  Would you care to try this approach on a shorter
>> input array, like
>> 
>> 	data = new int[] { Integer.MAX_VALUE };
>> 
>> This case should be quite simple, since the array is already sorted.
>> Let us know how you make out, will you?
>
>I didn't say it works for any array out there, did I?

     You did.  Claiming an algorithm is O(n) means claiming that that
is the upper bound.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#7927

On 9/12/2011 1:57 PM, Gene Wirchenko wrote:
> On Mon, 12 Sep 2011 01:40:50 +0200, Wanja Gayk<brixomatic@yahoo.com>
> wrote:
>> In article<j4jala$dkh$1@dont-email.me>, esosman@ieee-dot-org.invalid
>> says...
>>
>>>       Very nice!  Would you care to try this approach on a shorter
>>> input array, like
>>>
>>> 	data = new int[] { Integer.MAX_VALUE };
>>>
>>> This case should be quite simple, since the array is already sorted.
>>> Let us know how you make out, will you?
>>
>> I didn't say it works for any array out there, did I?
>
>       You did.  Claiming an algorithm is O(n) means claiming that that
> is the upper bound.

No - big O for algorithms is usual average case not worst case.

I am sure you can find plenty of quotes for quicksort being
O(nlogn) and not O(n^2).

Arne

[toc] | [prev] | [next] | [standalone]

#7943

On 9/12/2011 7:01 PM, Arne Vajhøj wrote:
> On 9/12/2011 1:57 PM, Gene Wirchenko wrote:
>> On Mon, 12 Sep 2011 01:40:50 +0200, Wanja Gayk<brixomatic@yahoo.com>
>> wrote:
>>> In article<j4jala$dkh$1@dont-email.me>, esosman@ieee-dot-org.invalid
>>> says...
>>>
>>>> Very nice! Would you care to try this approach on a shorter
>>>> input array, like
>>>>
>>>> data = new int[] { Integer.MAX_VALUE };
>>>>
>>>> This case should be quite simple, since the array is already sorted.
>>>> Let us know how you make out, will you?
>>>
>>> I didn't say it works for any array out there, did I?
>>
>> You did. Claiming an algorithm is O(n) means claiming that that
>> is the upper bound.
>
> No - big O for algorithms is usual average case not worst case.

     Big O is for whatever quantity it is measuring.

> I am sure you can find plenty of quotes for quicksort being
> O(nlogn) and not O(n^2).

     Quicksort takes O(n*log n) *average* time, O(n*n) *worst case*
time.  Neither of the Big O's is in any way "preferable" to the
other: They are describing different aspects of the algorithm.
There is no reason to *expect* "average time" and "worst case time"
and "time off for good behavior" to have similar Big-O expressions.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#7945

> On 9/12/2011 7:01 PM, Arne Vajhøj wrote:
>> No - big O for algorithms is usual average case not worst case.


I'm pretty sure that is not correct.  Quoting Wikipedia:

"Informally, especially in computer science, the Big O notation often is 
permitted to be somewhat abused to describe an asymptotic tight bound 
where using Big Theta Θ notation might be more factually appropriate in 
a given context."

That is to say, Big O is the upper bound.  Big Theta is the average case 
or the expected case.

<http://en.wikipedia.org/wiki/Big_O_notation>


>> I am sure you can find plenty of quotes for quicksort being
>> O(nlogn) and not O(n^2).

On 9/12/2011 6:29 PM, Eric Sosman wrote:
> Quicksort takes O(n*log n) *average* time, O(n*n) *worst case*
> time.


Both of these are also incorrect, I think.  The sort time for quick sort 
is O(n log n) for RANDOM data.  This can be proven.  The worst case is 
O(n^2) and that's for already sorted data, a not unreasonable input.  So 
the n log n number for quicksort is for a particular arrangement of 
data, not the actual upper bound.

The random data argument is a bit like the spaghetti sort.  It works 
well for certain types of input, like spaghetti, not so well with other 
types of data.

[toc] | [prev] | [next] | [standalone]

#7954

[no name] wrote:
>>  Arne Vajhøj wrote:
>>> No - big O for algorithms is usual average case not worst case.
> 
> I'm pretty sure that is not correct.  Quoting Wikipedia:
> 
> "Informally, especially in computer science, the Big O notation often is 
> permitted to be somewhat abused to describe an asymptotic tight bound 
> where using Big Theta Θ notation might be more factually appropriate in 
> a given context."
> 
> That is to say, Big O is the upper bound.  Big Theta is the average case 
> or the expected case.

O is upper bound.  Omega is lower bound.  Theta is both upper and lower, or "tight" bound.  Any of the three can describe average case, best case, expected case or worst case, according to what is being bounded.

As is explained by the very site you cite:

> <http://en.wikipedia.org/wiki/Big_O_notation>

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#7976

On 9/12/2011 9:49 PM, markspace wrote:
> That is to say, Big O is the upper bound. Big Theta is the average case
> or the expected case.

The first part of that statement I might accept as a simplification, 
while the second sentence I would definitely not.

f(x) = Theta(g(x)) if and only if lim x->inf f(x)/g(x) is neither 0 nor 
infinity; in other words, f(x) and g(x) have the same asymptotic 
behavior up to a constant.

Big-O really just means that the function will grow no faster than 
another; in a way, it's a pessimistic bound: you can prove that your 
function is O(n^3), but it could still be O(n^2) and you can't prove 
that it is. If a function is Theta(n^3), however, there is no way in 
hell that it could be O(n^2); you have proven that it is exactly cubic 
in all cases.

You can use any of these for best-case, average-case, or worst-case 
performance, although using big-O for the best-case performance is 
somewhat counterintuitive.

> Both of these are also incorrect, I think. The sort time for quick sort
> is O(n log n) for RANDOM data. This can be proven. The worst case is
> O(n^2) and that's for already sorted data, a not unreasonable input. So
> the n log n number for quicksort is for a particular arrangement of
> data, not the actual upper bound.

There are ways to touch up quicksort to achieve Theta(n lg n) time for 
sorted data, and the implementation in the JVM does so.

-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth

[toc] | [prev] | [next] | [standalone]

#8004

On 9/12/2011 10:49 PM, markspace wrote:
>> On 9/12/2011 7:01 PM, Arne Vajhøj wrote:
>>> No - big O for algorithms is usual average case not worst case.
>
> I'm pretty sure that is not correct. Quoting Wikipedia:
>
> "Informally, especially in computer science, the Big O notation often is
> permitted to be somewhat abused to describe an asymptotic tight bound
> where using Big Theta Θ notation might be more factually appropriate in
> a given context."
>
> That is to say, Big O is the upper bound. Big Theta is the average case
> or the expected case.
>
> <http://en.wikipedia.org/wiki/Big_O_notation>

I don't think upper bound in this case means worst case.

See:
 
http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations

>>> I am sure you can find plenty of quotes for quicksort being
>>> O(nlogn) and not O(n^2).
>
> On 9/12/2011 6:29 PM, Eric Sosman wrote:
>> Quicksort takes O(n*log n) *average* time, O(n*n) *worst case*
>> time.
>
>
> Both of these are also incorrect, I think. The sort time for quick sort
> is O(n log n) for RANDOM data. This can be proven. The worst case is
> O(n^2) and that's for already sorted data, a not unreasonable input. So
> the n log n number for quicksort is for a particular arrangement of
> data, not the actual upper bound.
>
> The random data argument is a bit like the spaghetti sort. It works well
> for certain types of input, like spaghetti, not so well with other types
> of data.

O(n*logn) is by far the most likely. Which is why that is usually given
as the big O for QS when it is not mentioning both average and worst
case.

But it is possible to have data with O(n^2).

Note that this worst case is only sorted data when using the
first or last element as pivot element. If you use the middle
element as pivot element, then QA works perfectly for sorted data.

(there are the same number of worst cases, but sorted is
just not one of them)

Arne

[toc] | [prev] | [next] | [standalone]

#8026

On Tue, 13 Sep 2011 21:51:13 -0400, Arne Vajhøj <arne@vajhoej.dk>
wrote:

>On 9/12/2011 10:49 PM, markspace wrote:
>>> On 9/12/2011 7:01 PM, Arne Vajhøj wrote:
>>>> No - big O for algorithms is usual average case not worst case.
>>
>> I'm pretty sure that is not correct. Quoting Wikipedia:
>>
>> "Informally, especially in computer science, the Big O notation often is
>> permitted to be somewhat abused to describe an asymptotic tight bound
>> where using Big Theta ? notation might be more factually appropriate in
>> a given context."
>>
>> That is to say, Big O is the upper bound. Big Theta is the average case
>> or the expected case.
>>
>> <http://en.wikipedia.org/wiki/Big_O_notation>
>
>I don't think upper bound in this case means worst case.

     Well, yes, it is.  That is why it is the upper bound.  If a worse
case were possible, then that limit would not be the upper bound.

[snip]

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#7969

On 9/12/2011 6:29 PM, Eric Sosman wrote:
...
> Big O is for whatever quantity it is measuring.
...

Another way of saying this is that Big-O is a relationship between
functions, that is, "f(x) is O(g(x))" is defined for a pair of functions
f and g.

Typically, f(x) is some measure of algorithm performance, such as the
worst case time for input of size x, and g(x) is a simpler function.

If f(x) is not the worst case time, I think it should be specified. If
f(x) is the worst case time and is O(g(x)) then the average and minimum
times are also O(g(x)).

Patricia

[toc] | [prev] | [next] | [standalone]

#7977

On Mon, 12 Sep 2011 19:01:26 -0400, Arne Vajhøj <arne@vajhoej.dk>
wrote:

>On 9/12/2011 1:57 PM, Gene Wirchenko wrote:
>> On Mon, 12 Sep 2011 01:40:50 +0200, Wanja Gayk<brixomatic@yahoo.com>
>> wrote:

[snip]

>>> I didn't say it works for any array out there, did I?
>>
>>       You did.  Claiming an algorithm is O(n) means claiming that that
>> is the upper bound.
>
>No - big O for algorithms is usual average case not worst case.

     Nope.  It is abused for that.

>I am sure you can find plenty of quotes for quicksort being
>O(nlogn) and not O(n^2).

     And that is an example of the abuse.  Quicksort is nearly O(n log
n), but technically, it is O(n squared).

     I am sure that I can find plenty of quotes for the moon being
made of green cheese, too.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#7508

On 8/31/2011 10:48 PM, KevinSimonson wrote:
> I have an<enum>  named<ProjectEnum>  that has twelve values.  Today I
> added an instance variable to it, a<String>  named<collectionTitle>.
> The engineer I'm working with asked me to write a static method in
> class<ProjectEnum>  that returns an array of<ProjectEnum>s sorted
> alphabetically by this value<collectionTitle>.
>
> I wrote a little program that compares the performance of
> SelectionSort and InsertionSort on comparable arrays of<String>s, and
> discovered that InsertionSort sorts in about half the amount of time
> that InsertionSort does, at least on our machines.  Therefore I
> implemented my static method,<alphaSort()>, using InsertionSort.

     Failed to find Arrays.sort, did you?

> On the way home from work my fellow carpooler told me that there are
> Java classes that can do sorts in O(N) time.

     Possible, perhaps, for restricted key types and given some
assumptions about the possible values: For instance, it's easy to
sort an array of `boolean' in O(N) time.  But quite clearly *not*
possible for sorts based on pairwise comparisons, since log(N!)
grows faster than O(N).

> That would be an
> improvement, since although InsertionSort is faster than
> SelectionSort, it's still an O(N^2) algorithm.

     So?  N in your case is twelve.  There's no point in studying the
behavior "as twelve approaches infinity," becase it doesn't.

     Besides, you're misusing O.  Suppose I offer you two algorithms,
one whose running time is O(N^2) and the other O(N).  Which is faster?
Before you say "O(N), nitwit," let me show you the actual timing
formulae:

	T1(N) = N * N (nanoseconds)
	T2(N) = N (gigayears)

T1(N) is clearly O(N^2), while T2(N) is O(N).  Which do you choose
for sorting N=12 items?

> So I went looking, but
> all I could find was the<sort()>  method from the<Collections>
> class.

     Either your looking was extremely cursory, or you haven't learned
how to look.  I'm not sure how you found Collections.sort, but *if*
you had opened the Javadoc, gone to the "S" index page, and hunted for
the word "sort," you'd have found Arrays.sort right next door to it.

> I replaced my code for SelectionSort with a loop that reads
> the input array into an<ArrayList<  String>>  object, calls<sort()>  on
> the<ArrayList<  String>>  object, and then reads the values back into
> the array; and then ran my test code again.  This method was
> significantly faster than SelectionSort, but my InsertionSort code
> still beat it.

     Your improved Javadoc searching skills would have found Arrays.sort,
which might have directed your attention to the Arrays class as a whole
and led you to discover Arrays.asList.  Or possibly not, because you
have no need of a List anyhow.  Meanwhile you've run "seven times around
the seven hills of Rome," and it's no surprise that the unnecessary trip
has made your task take longer than it needed to.

> So I guess my question is,<b><i>is</i></b>  there a way in Java to
> sort an array of<String>s (or perhaps more to the point to sort an
> array of<ProjectEnum>s) that runs in O(N) time?  Or even that runs in
> O(N^2) time but faster than InsertionSort?  I'd appreciate any
> information anyone can give me on this.

     Probably nothing of O(N); see remarks above.  Also probably
nothing as bad as O(N^2), but you can always do the hills of Rome
thing to slow down a better method if you want.

     BUT, BUT, BUT!  Your N is a constant, a small constant!  Even if
your hand-crafted sort runs at ten times the speed of Arrays.sort,
I posit that you have already expended more time than your speedy
method will ever recoup: If Arrays.sort takes a microsecond while
yours takes 100 nanoseconds, and if all your investigation and
implementation (and writing to Usenet) took just ten minutes, you
need more than six hundred billion fast sorts merely to break even.
Modify the arithmetic as needed in light of your actual measurements,
then turn your talents elsewhere instead of wasting them on a non-
problem.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#7509

On 9/1/2011 12:25 AM, Eric Sosman wrote:
>[...] If Arrays.sort takes a microsecond while
> yours takes 100 nanoseconds, and if all your investigation and
> implementation (and writing to Usenet) took just ten minutes, you
> need more than six hundred billion fast sorts merely to break even.

     "For suitable values of a billion," like those that begin
with an "M" instead of a "B."

     <FX: dope slap>

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#7514

Eric Sosman wrote:

> Besides, you're misusing O. Suppose I offer you two algorithms,
> one whose running time is O(N^2) and the other O(N). Which is faster?
> Before you say "O(N), nitwit," let me show you the actual timing
> formulae:
>
> T1(N) = N * N (nanoseconds)
> T2(N) = N (gigayears)
>
> T1(N) is clearly O(N^2), while T2(N) is O(N). Which do you choose
> for sorting N=12 items?

Conversely, Jon Bentley in an (evidently...) old book gives
an example (with implementations and timings)
where quicksort on a TRS-80 outperforms
bubble sort on a Cray-1.

I forget his value of 'N'.

  BugBear

[toc] | [prev] | [next] | [standalone]

#7524

On 9/1/2011 4:20 AM, bugbear wrote:
> Eric Sosman wrote:
>
>> Besides, you're misusing O. Suppose I offer you two algorithms,
>> one whose running time is O(N^2) and the other O(N). Which is faster?
>> Before you say "O(N), nitwit," let me show you the actual timing
>> formulae:
>>
>> T1(N) = N * N (nanoseconds)
>> T2(N) = N (gigayears)
>>
>> T1(N) is clearly O(N^2), while T2(N) is O(N). Which do you choose
>> for sorting N=12 items?
>
> Conversely, Jon Bentley in an (evidently...) old book gives
> an example (with implementations and timings)
> where quicksort on a TRS-80 outperforms
> bubble sort on a Cray-1.

     I think it was in a CACM column; can't remember whether it was
part of his "Programming Pearls" series or not.  The latter have
been collected in book form.

> I forget his value of 'N'.

     So do I.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#7520

On Thu, 01 Sep 2011 00:25:04 -0400, Eric Sosman
<esosman@ieee-dot-org.invalid> wrote, quoted or indirectly quoted
someone who said :

>     Either your looking was extremely cursory, or you haven't learned
>how to look.  I'm not sure how you found Collections.sort, but *if*
>you had opened the Javadoc, gone to the "S" index page, and hunted for
>the word "sort," you'd have found Arrays.sort right next door to it.

Here are three techniques to see if Java has some built-in capability.

You need an indexing tool like Copernic to find plausible method names
in the JavaDoc that you can download and insert in the JDK.

Alternatively you can use a tool like Funduc Search and replace or
Extract http://mindprod/products1.html#EXTRACT to linearly search for
regular expressions.

The other technique is to Google something like [sort Java array] and
see what code pops up. Look for the relevant classes and consult the
Javadoc.
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
The modern conservative is engaged in one of man's oldest exercises in moral philosophy; that is, 
the search for a superior moral justification for selfishness.
~ John Kenneth Galbraith (born: 1908-10-15 died: 2006-04-29 at age: 97) 

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web