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 3 of 3 — ← Prev page 1 2 [3]

#7510

On 01.09.2011 04:48, 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>.

Since we're talking about an enum and I am sure you made field "name" 
final (i.e. to make instances immutable) you can completely ignore sort 
performance.  You just need to sort once.  For example:

package en;

import java.util.Arrays;
import java.util.Comparator;

public enum ProjectEnum {

   P1("xyz"), P2("abc"), P3("def");

   private final String collectionTitle;

   private ProjectEnum(String name) {
     if (name == null) {
       throw new NullPointerException();
     }

     this.collectionTitle = name;
   }

   public String getCollectionTitle() {
     return collectionTitle;
   }

   private static final ProjectEnum[] sortedValues;

   static {
     sortedValues = ProjectEnum.values();

     Arrays.sort(sortedValues, new Comparator<ProjectEnum>() {
       @Override
       public int compare(ProjectEnum o1, ProjectEnum o2) {
         return o1.getCollectionTitle().compareTo(o2.getCollectionTitle());
       }
     });
   }

   public static ProjectEnum[] sorted() {
     return Arrays.copyOf(sortedValues, sortedValues.length);
   }
}

Kind regards

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

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

#7517

On 01/09/2011 03:48, 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>.
>
>
> is 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.


If I was sorting twelve elements, I would consider myself utterly 
deranged if I found myself worrying about the sort algorithm.



If the static method will be called millions of times per second, you 
might want to cache the sort results rather than pointlessly repeating 
the sort, but only after measuring a performance problem and working out 
if this method really needs to be called that often.

-- 
RGB

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

#7522

On 9/1/2011 2:08 AM, RedGrittyBrick wrote:
> On 01/09/2011 03:48, 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>.
>>
>>
>> is 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.
>
>
> If I was sorting twelve elements, I would consider myself utterly
> deranged if I found myself worrying about the sort algorithm.
>
>
>
> If the static method will be called millions of times per second, you
> might want to cache the sort results rather than pointlessly repeating
> the sort, but only after measuring a performance problem and working out
> if this method really needs to be called that often.
>

The simplest solution to this would be to use Arrays.sort, and forget
about it. If anything else, such as caching, is needed, there will be a
reminder in the form of Arrays.sort taking a significant fraction of the
run time.

Patricia

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

#7518

On Wed, 31 Aug 2011 19:48:02 -0700 (PDT), KevinSimonson
<kvnsmnsn@hotmail.com> wrote, quoted or indirectly quoted someone who
said :

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

The bulit-in sort in Java beats everything I have thrown at it except
a RadixSort for some cases.  I have posted the code for a number of
different algorithms, including RadixSort, HeapSort, BubbleSort,
ShellSort, QuickSort. InsertionSort and SelectionSort are too
disgusting to code.

See http://mindprod.com/jgloss/sort.html

I have also written an applet that generates Comparator/Comparable
classes. 
See http://mindprod.com/applet/comparator.html

Java has a built-in sort mechanism with Comparator and Comparable
interfaces. Even if you experiment with your own sorts, they should
use the standard interface.
-- 
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]

#7523

On Wed, 31 Aug 2011 19:48:02 -0700 (PDT), KevinSimonson
<kvnsmnsn@hotmail.com> wrote, quoted or indirectly quoted someone who
said :

>I have an <enum> named <ProjectEnum> that has twelve values

have a look at the sample code at
http://mindprod.com/jgloss/enum.html#SORTING

It sorts an array of enums both by the default ordinal and using a
custom Comparator.


You can generate Comparators with 
http://mindprod.com/applet/comparatorcutter.html
-- 
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]

#7525

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

[toc] | [prev] | [standalone]

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

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

csiph-web