Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

sorting algorithm  RSS feed

 
joe weakers
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi there. I have a Vector v of InterestFeature objects that has a constant size of 27. In my class InterestFeature, I have set and get methods for setting and getting the InterestFeature objects' names and current scores. Therefore all the objects in v have a name and current score associated with them. What I need to do now is to parse thru all the elements in v and insert the objects' names into a new data structure x in the order of their current scores, i.e. for each value in v insert it into x based on its score where the values in x are ordered from highest score to lowest score. I know there are stacks, lists, sorting algorithms, etc. out there but I was hoping that somebody might save me the hassle of spending a lot of effort finding the most suitable solution. Thnaks a lot, Joe
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd simply use a TreeSet.
 
joe weakers
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Cheers Ilja. Thanks for your reply. I had a look in the javadocs for information about TreeSets but I struggled to find any examples of its implementation. Is there any chance that you may know of a link to an example of how a TreeSet is implemented. Sorry but I am having difficulty getting my head around the javadocs. Joe
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13078
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Assuming you plan to use the java.util.TreeSet, (or TreeMap) it is really very simple. You just need to provide a Comparator that understands your ordering function. Your InterestFeature objects would be the key and the name the stored value. The iteration order would be that defined by the Comparator.

HOWEVER! Note that if the scores or other values are changed after the object is added to the set, the order will NOT be fixed up. Much better to create a temporary TreeSet whenever you need the sorted order.
Bill
 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note also that if two InterestFeature objects have the same score, using either TreeMap or TreeSet will result in those duplicates being removed. If you need this sorted list every so often (not constantly up-to-date), I'd simply create a new List and sort it each time you need it. If you can't use the new Collections (List, Collections.sort(), etc), you'll have to find another solution. You might want to replace your usage of Vector with its equivalent ArrayList as well.The Comparator may need tweaking if I got the ordering wrong (see the JavaDocs) or if the values get large and small enough to cause overflow or if they're not so simple.

In any case, after this code runs, the sorted List should be in descending score order. Simply iterate it to get the names.
 
Stefan Wagner
Ranch Hand
Posts: 1923
Linux Postgres Database Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With 27 elements, nearly every algorithm (beside divine sorting) should work in acceptable time (even on an 386-PC).

Divine sorting: insert all elements by random, and check whether they are sorted the right way. Repeat if not.
[ January 22, 2005: Message edited by: Stefan Wagner ]
 
Gary Bentley
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you want a "general" purpose solution that allows you to perform the search and reconfigure the ordering without having to write any code, see: http://josql.sourceforge.net

It then will allow you to do stuff like:

SELECT *
FROM InterestFeature
ORDER BY score DESC, name
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13078
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What a cool toolkit/concept Gary! Thanks for pointing that out.
Bill
 
joew weakers
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi guys. Thanks a lot for all your replies. I implemented a List data structure and now everything works perfectly. However, I wanted to use the same List approach to sort an array of "Layer" objects in alphabetical order based on the layer names. My code looks as follows:

java.util.List layers = Arrays.asList(LH.getLayers());
Collections.sort(layers, new Comparator(){
public int compare(Object x, Object y){
//compare layers based on layer name - String values
return((Layer) x).getName().compareTo((Layer) y).getName(); //error here
}
});

I get the following error when I try to compile this code.

Error: object type required, but int found

Perhaps I am approaching this from the wrong angle. Can anyone offer me some advice here. Joe
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by joew weakers:
I get the following error when I try to compile this code.

Error: object type required, but int found


As this seems to be a new question, that isn't related to performance any more, I'd advise you to post this as a new question in one of the Java in General forums. And please use code tags when doing so.
 
David Harkness
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by joew weakers:
If this is pasted from your source and not a retyping, you've missed an extra open parenthesis in the second cast and a close parenthesis for the compareTo() call:As you have it, you're passing y to compareTo() and calling getName() on the returned int -- thus the "not an Object" error.
[ February 03, 2005: Message edited by: David Harkness ]
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!