File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes More elegant sort of LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "More elegant sort of LinkedList" Watch "More elegant sort of LinkedList" New topic
Author

More elegant sort of LinkedList

Ruben Steins
Greenhorn

Joined: Nov 22, 2002
Posts: 15

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?

Grtz. Ruben
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
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
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
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
Greenhorn

Joined: Nov 22, 2002
Posts: 15

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
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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.


"I'm not back." - Bill Harding, Twister
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: More elegant sort of LinkedList
 
Similar Threads
I don't know what's wrong with this chess game
getting a Null pointer exception at this point
Help.....Thread
can we have array of ArrayLists