Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

More elegant sort of LinkedList

 
Ruben Steins
Greenhorn
Posts: 15
Chrome IntelliJ IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 15
Chrome IntelliJ IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic