More elegant sort of LinkedList

[Ruben Steins]

Hi all,
The code below compiles fine and all, and does what it's supposed to do, but it seems a very unelegant way to do a selection sort on a LinkedList.
I want to sort the Objects in this LinkedList (which are of a class called Klus (dutch fot job btw)) by one of the class variables namely priority.
There must be better/cleaner ways to perform this? Any suggestions?

private void sortQueue( LinkedList queue )
        {
          /** This method will sort the queue
           * by klus.priority to make sure
           * important jobs get done first!
           * using a crude selection-sort
           */
          for( int i = 0; i < queue.size(); i++ )
          {
            int min = i;
            for( int j = i + 1; j < queue.size(); j++ )
            {
              Klus k1 = new Klus();
              k1 = (Klus)queue.get( j );
              Klus k2 = new Klus();
              k2 = (Klus)queue.get( min );
              if( k1.prioriteit < k2.prioriteit ) min = j;
            }
            Klus tempKlus = new Klus();
            tempKlus = (Klus)queue.get( i );
            queue.set( i, (Klus)queue.get( min ) );
            queue.set( min, tempKlus );
          }
        }  

Grtz. Ruben

[David Weitzman]

LinkedLists are quite slow to sort -- if the list is more than a handfull of elements long you'd be better off using an ArrayList. Worst case scenario you should copy the data to an ArrayList, sort it, and copy it back. Anyway...
When it doubt, call Collections.sort(). You get O(n log n) performance in one line without even breaking into a sweat.

[David Weitzman]

You'll need to implement Comparable or write a Comparator. See the Collections.sort() javadocs for a cycle of links that eventually lead to either annoyance or enlightenment.

[Ruben Steins]

Originally posted by David Weitzman:
Worst case scenario you should copy the data to an ArrayList, sort it, and copy it back.
...
When it doubt, call Collections.sort().

It seems this is excactly what Collections.sort does

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place

But does this mean I have to write my own compare method for the Klus-class and use this for sorting (with the specs from the API)?

[Jim Yingst]

Yes - either a compareTo(Object) method within the Klus class, making it implement Comparable - or a compare(Object, Object) method in a separate class which implements Comparator.