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 1 of 3  [1] 2 3  Next page →

#7506 — Using Java Classes to Sort a Small Array Quickly

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.

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.  So I went looking, but
all I could find was the <sort()> method from the <Collections>
class.  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.

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.

Kevin Simonson

[toc] | [next] | [standalone]

#7507

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.


> my InsertionSort code
> still beat it.


How many projects can you have?  For small arrays anything is fast and 
even a bubble sort should work fine.  If you have many projects... how 
do you code that up as an enum anyway?

Sorry but there's a little red flashing light labeled "warning!" that's 
going off in my mind right now.

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

#7513

markspace wrote:
> 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.

You might want to look up radix sort, which is only applicable
in special (but quite common) cases. Not relevant to the OP,
of course.

  BugBear

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

#7519

On Wed, 31 Aug 2011 20:39:09 -0700, markspace <-@.> wrote, quoted or
indirectly quoted someone who said :

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

see http://mindprod.com/jgloss/radixsort.html

Surely you remember mechanical card sorters. They did precisely that.
-- 
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]

#7521

On 9/1/2011 2:38 AM, Roedy Green wrote:
> On Wed, 31 Aug 2011 20:39:09 -0700, markspace<-@.>  wrote, quoted or
> indirectly quoted someone who said :
>
>>
>> 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.

The proof of the n log n minimum only applies to comparison sorts.

> see http://mindprod.com/jgloss/radixsort.html
>
> Surely you remember mechanical card sorters. They did precisely
> that.

If I had needed to sort twelve punch cards, I would have done it by
hand, in far less time than it would have taken to walk from my desk to
a mechanical sorter. Fortunately, I never had a desk in same room as a
card sorter. For small problems, overhead time is far more important
than asymptotic behavior.

Patricia

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

#7824

In article <j3mupc$d5m$1@dont-email.me>, -@. 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;
    }
   }
  }
 }


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]

#7829

On 9/11/2011 5:14 PM, Wanja Gayk wrote:
> In article<j3mupc$d5m$1@dont-email.me>, -@. 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
esosman@ieee-dot-org.invalid

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

#7842

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?

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]

#7847

On 9/11/2011 7:40 PM, Wanja Gayk 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?

     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
esosman@ieee-dot-org.invalid

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

#8095

In article <j4jjuv$579$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?
> 
>      Ah.  Then I claim I can sort an array of integers in O(0) time.
> (And my claim is O(as worthwhile) as yours.)

Those constraints would be pretty useless though. On the other hand: 
Sorting numbers of a limited range is pretty common.
Either way I would argue that sorting an empty or one-element array is 
no sorting at all.

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]

#8098

On 9/16/2011 8:54 PM, Wanja Gayk wrote:
> In article<j4jjuv$579$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?
>>
>>       Ah.  Then I claim I can sort an array of integers in O(0) time.
>> (And my claim is O(as worthwhile) as yours.)
>
> Those constraints would be pretty useless though. On the other hand:
> Sorting numbers of a limited range is pretty common.
> Either way I would argue that sorting an empty or one-element array is
> no sorting at all.

     Fine.  Then sort

	data = new int[] { Integer.MAX_VALUE, 1, 3, 1, 4, 1, 5, 9 };

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

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

#8104

In article <j50rk7$huc$1@dont-email.me>, esosman@ieee-dot-org.invalid 
says...

> > Those constraints would be pretty useless though. On the other hand:
> > Sorting numbers of a limited range is pretty common.
> > Either way I would argue that sorting an empty or one-element array is
> > no sorting at all.
> 
>      Fine.  Then sort
> 
> 	data = new int[] { Integer.MAX_VALUE, 1, 3, 1, 4, 1, 5, 9 };

You don't get it, do you?
Which part of "limited range" was too hard to understand for you?

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]

#8106

On 9/17/2011 10:52 AM, Wanja Gayk wrote:
> In article<j50rk7$huc$1@dont-email.me>, esosman@ieee-dot-org.invalid
> says...
>
>>> Those constraints would be pretty useless though. On the other hand:
>>> Sorting numbers of a limited range is pretty common.
>>> Either way I would argue that sorting an empty or one-element array is
>>> no sorting at all.
>>
>>       Fine.  Then sort
>>
>> 	data = new int[] { Integer.MAX_VALUE, 1, 3, 1, 4, 1, 5, 9 };
>
> You don't get it, do you?
> Which part of "limited range" was too hard to understand for you?

     My apologies.  I should have asked you to sort

	new int[] { Integer.MAX_VALUE,
	            Integer.MAX_VALUE - 1,
	          };

... an array whose range spans only two values.

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

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

#8126

In article <j52d0i$98i$1@dont-email.me>, esosman@ieee-dot-org.invalid 
says...

>      My apologies.  I should have asked you to sort
> 
> 	new int[] { Integer.MAX_VALUE,
> 	            Integer.MAX_VALUE - 1,
> 	          };
> 
> ... an array whose range spans only two values.

Which are both out of range.

http://r3dux.org/wp-content/uploads/2010/09/Trolling-Is-A-Art.jpg

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]

#8137

Wanja Gayk wrote:
> esosman@ieee-dot-org.invalid says...
>>      My apologies.  I should have asked you to sort
>> 
>> 	new int[] { Integer.MAX_VALUE,
>> 	            Integer.MAX_VALUE - 1,
>> 	          };
>> 
>> ... an array whose range spans only two values.
> 
> Which are both out of range.
> 
> http://r3dux.org/wp-content/uploads/2010/09/Trolling-Is-A-Art.jpg

Eric isn't trolling, he's making a technical point.  The only thing you might find trollish about his remarks is that they completely contradict your points on technical merit, but rejecting technically valid counterpoint by calling it trolling is itself a trollish ploy.

You kept changing the ground of your assertions, which is itself trolling behavior.  You first claim that you aren't talking about all data sets, a point which contradicts your use of big-O notation.  Then you told Eric, "On the other hand: Sorting numbers of a limited range is pretty common."  So Eric provides TWO examples of sorting numbers of a limited range, and you reject both scenarios.  This one you refer to some mythical predetermined range out of which you claim Eric's values are.  Huh?  What range is that, and who made you the Range Czar?

You cannot make a big-O assertion about one data set.  The concept is meaningless.  Asymptotic notation is about algorithmic convergence as problem size grows.

Eric's answer and example were perfectly valid technical challenges to your technical assertions.  Instead of answering him fairly and showing how your general statements apply to his particular counterexample, you wave your hands vaguely and refer to some non-existent criteria not previously stated, and accuse him of trolling when he wasn't.  This actually renders your points invalid.

You can't make algorithmic claims about one particular data set!  Especially when you don't reveal what that data set is.

-- 
Lew

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

#8142

On 9/18/2011 12:53 PM, Lew wrote:
> Wanja Gayk wrote:
>> esosman@ieee-dot-org.invalid says...
>>> My apologies.  I should have asked you to sort
>>>
>>> new int[] { Integer.MAX_VALUE, Integer.MAX_VALUE - 1, };
>>>
>>> ... an array whose range spans only two values.
>>
>> Which are both out of range.
>>
>> http://r3dux.org/wp-content/uploads/2010/09/Trolling-Is-A-Art.jpg
>
> Eric isn't trolling, he's making a technical point.  The only thing
> you might find trollish about his remarks is that they completely
> contradict your points on technical merit, but rejecting technically
> valid counterpoint by calling it trolling is itself a trollish ploy.

Although I think there are better examples, Wanja Gayk's basic technical
point is absolutely correct. The commonly stated \Omega(n log n) bound
has been proved for comparison sorts, but not for sorting in general,
and there are O(n) sorts.

Patricia

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

#7848

On 9/11/2011 7:40 PM, Wanja Gayk 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?

No.

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

Arne

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

#7856

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.

-- 
Lew

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

#7928

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

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

#7934

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.

> 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

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web