«

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
d

On 8/31/2011 9: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>.

Let me start by pointing out: you have 12 elements in your array to
sort. Any sort you pick, short of bogosort, would complete in at most a
millisecond or two, even on crappy old hardware.

> On the way home from work my fellow carpooler told me that there are
> Java classes that can do sorts in O(N) time. That would be an
> improvement, since although InsertionSort is faster than
> SelectionSort, it's still an O(N^2) algorithm.

The big-O notation is used to indicate asymptotic execution time, so
it's more useful if you're talking about high values of N (billions are
not unheard of in graph theory). At low values of N, the overhead in
setting up and per-element stuff can dominate the runtime.

The standard sort methods are quicksort (used in Java for primitive
arrays) and mergesort (used in Java for arrays of reference types).
These are both implemented recursively. However, recursion induces a
high overhead cost (setting up and tearing down the function stack isn't
cheap, and in these cases also involves yet another linear scan, etc.),
so when the array size is very small, it just sorts the array using
insertion sort. I do not recall the magic cutoff point off the top of my
had, but I believe it is between 8 and 16.

I would also like to point out that no comparison sort is capable of
achieving faster than O(n lg n) time in the worst case. Things like
radix sort can achieve O(n), at the cost of being dependent on the size
of the input, so they are less generally usable. Boolean sort and
possibly byte sort (given the extremely low numbers of values these can
attain) actually do use this sort of algorithm in Java.

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

Actually, Arrays.sort is the "main" sort method[s]: if you look at the
code for Collections.sort, it extracts the elements into an array, sorts
that array, and then reinserts the method in the Collections in order.
If you originally have an array, Arrays.sort will save you 4 buffer
copies. Since you commented that your insertion sort beat this method, i
am betting that it's the multiple copies that is making it slower than
your hand-built sort.

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

On 9/11/2011 5:14 PM, Wanja Gayk wrote:
> In article<j3mupc$d5m$>, -@. says...
>>
>> On 8/31/2011 7:48 PM, KevinSimonson wrote:
>>> On the way home from work my fellow carpooler told me that there are
>>> Java classes that can do sorts in O(N) time.
>>
>>
>> Pfft. No. Theoretical maximum speed of a sort is something like n log
>> n. The only data you can sort in n time is data that's already sorted.
>
> Wrong.
> Here's the proof: Sorting an array of positive integers in O(n) time:
>
> public static void main(final String[] args) {
> final int[] data = new int[]{3,7,6,3,5,4,1,3,1,1,1,3,4,6,0,0};
> System.out.println(Arrays.toString(data));
> sort(data);
> System.out.println(Arrays.toString(data));
> }
>
> private static void sort(final int[] data) {
> if (data.length> 0) {
> long max = Long.MIN_VALUE;
> for (final int t : data) {
> max = Math.max(t, max);
> }
> final long[][] buckets = new long[(int) max+1][data.length];
> for (final long[] bucket : buckets) {
> Arrays.fill(bucket, Long.MIN_VALUE);
> }
> for (final int x : data) {
> for (int y = 0; y< buckets[x].length; ++y) {
> if (buckets[x][y] == Long.MIN_VALUE) {
> buckets[x][y] = x;
> break;
> }
> }
> }
> int x = -1;
> for (long[] bucket : buckets) {
> for (long value : bucket) {
> if (value == Long.MIN_VALUE) {
> break;
> }
> data[++x] = (int) value;
> }
> }
> }
> }

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?

--
Eric Sosman
d

On 9/11/2011 7:40 PM, Wanja Gayk wrote:
> In article<j4jala$dkh$>, d
> 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?

Ah. Then I claim I can sort an array of integers in O(0) time.
(And my claim is O(as worthwhile) as yours.)

--
Eric Sosman
d

On 9/11/2011 7:40 PM, Wanja Gayk wrote:
> In article<j4jala$dkh$>, d
> 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?

No.

But a solution is a bit more practical if it does.

Arne

Arne Vajhøj wrote:
> Wanja Gayk wrote:
>> d 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 particulardata set is irrelevant to a discussion of asymptotic performance. The hubof the joke was his reference to "O(n)" and calling it "proof" when he wasmaking no statement about asymptotic performance.

I get it.

--
Lew

On Mon, 12 Sep 2011 01:40:50 +0200, Wanja Gayk <>
wrote:

>In article <j4jala$dkh$>, d
>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

On 9/12/2011 1:57 PM, Gene Wirchenko wrote:
> On Mon, 12 Sep 2011 01:40:50 +0200, Wanja Gayk<>
> wrote:
>> In article<j4jala$dkh$>, d
>> 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

On 9/11/2011 11:30 PM, Lew wrote:
> Arne Vajhøj wrote:
>> Wanja Gayk wrote:
>>> d 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.

Asymptotically for n going against infinity.

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

His code is an example of code - the proof should be in most algorithmic
books.

It is not unheard of for a practical implementation of a sort to have
some limitations.

But usually it is for extreme cases.

Not being able to sort an array with one huge element is
a real problem for practical usage.

Arne

Arne Vajhøj wrote:
> Lew wrote:
> > Arne Vajhøj wrote:
> >> Wanja Gayk wrote:
> >>> d 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. Thehub of the joke was his reference to "O(n)" and calling it "proof" when hewas 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.

> Asymptotically for n going against infinity.

As long as you don't hit the worst case. But you are correct that the average case is what is important.

> Big O for execution speed traditionally does not look at
> memory restrictions and data type restrictions.
>
> His code is an example of code - the proof should be in most algorithmic
> books.
>
> It is not unheard of for a practical implementation of a sort to have
> some limitations.
>
> But usually it is for extreme cases.
>
> Not being able to sort an array with one huge element is
> a real problem for practical usage.

--
Lew