Can somebody help me with some Java programming?

April 8, 2010 10:46 PM

Can someone help me with some Java programming?

Okay, so my task is this: I'm given an ArrayList of Strings with a bunch of random words with capitalized letters. They typically are around 4-5 words long and are apparently also generally the name of a fruit, like "APPLE", "ORANGE", "PEAR", and so forth. Anyway, I have to code a method which receives this ArrayList as a parameter and then displays the string elements in some form in alphabetical order, leaving the original ArrayList unchanged. The basic idea seems to somehow be able to assign value or precedence to each letter of the String elements of the ArrayList so that the elements can be sorted alphabetically. I was thinking of coding a helper method which would traverse the ArrayList and for each word would add an Integer object to a second ArrayList that would represent the String element in the original ArrayList according to each letter's place in the alphabet. For example, if "APPLE" were the third element in the original ArrayList, then the third element in the second ArrayList would be "01616125." However, now that I look at it, I have no idea how my original method is going to be able to know whether two digits represent one letter or two. Damn. At any rate, the basic idea again seems to somehow be able to assign some kind of value or precedence to each letter of the String elements so that the elements can be sorted. Any suggestions?

posted by bookman117 to Technology (15 answers total)

Create a copy of the arraylist and sort it. Naive, but it satisfies your conditions.

There is a better way, but I haven't written a line of java in years
posted by sanko at 10:52 PM on April 8, 2010

Best answer: public void sort(ArrayList a){
    ArrayList b = Collections.sort(new ArrayList(a));
    for(String s : b) System.out.println(s);
}

This works because strings have an intrinsically Lexicographical Order, and so they are as easy to sort as regular numbers

Also, check out stack overflow for programming questions, it's a great site.
posted by delmoi at 10:56 PM on April 8, 2010

Also, if you ever have to sort something that doesn't already have a built in ordering, or sort them in a different way, you can create a Comparator and use that with the basic libraries. So for example if you wanted to sort the strings by last letter first or something. Or use a lookup table to sort by number of calories, whatever.
posted by delmoi at 11:00 PM on April 8, 2010

This works because strings have an intrinsically Lexicographical Order, and so they are as easy to sort as regular numbers

Not sure if Java is reliant on UNIX environment variables to decide how to sort, when a Java app is run on a non-Windows client, but in UNIX what lexicographical order is may not always be consistent.
posted by Blazecock Pileon at 11:08 PM on April 8, 2010

Java is pretty well machine independent, and the sorting will be done properly across machines, with capital letters taking precedence over lowercase letters.
posted by Precision at 11:25 PM on April 8, 2010

Yeah, the documentation for the String class is pretty explicit -- it sorts lexicographically by Unicode character values.
posted by teraflop at 11:41 PM on April 8, 2010

delmoi's answer is almost there, but Collections.sort sorts in place and returns void, rather than returning the sorted list. Instead:

public void sort(List<String> unsorted){
    List<String> sorted = new ArrayList<String>(unsorted);
    Collections.sort(sorted);
    return sorted;
}

will work.

The "attach an integer and sort by that" approach is very rarely the right thing to do - it might be an okay approach when your sort performance matters and calculating the sort order is expensive.

Instead, if you do need to do some sort of transform on the object before comparing it:

Collections.sort(sorted, new Comparator<String>(){
  public int compare(String a, String b) { 
    return a.toLowerCase().compareTo(b.toLowerCase());
});

(Ah - but in checking the JavaDoc, I've just discovered Collections.sort(sorted, String.CASE_INSENSITIVE_ORDER), which will do the same thing in this case.
posted by siskin at 12:59 AM on April 9, 2010

delmoi's answer is almost there, but Collections.sort sorts in place and returns void, rather than returning the sorted list.

I did create a new list, but I didn't notice that collections.sort() returns void. Normally if I need something sorted, I just keep it in a sorted collection to begin with.
posted by delmoi at 1:37 AM on April 9, 2010

Oops, and I got it wrong too - forgot to change the return type on the sort method:

public List<String> sort(List<String> unsorted){
    List<String> sorted = new ArrayList<String>(unsorted);
    Collections.sort(sorted);
    return sorted;
}

posted by siskin at 1:49 AM on April 9, 2010

You could do it a bit faster like this:


public List sort(List unsorted) {
return new TreeList(unsorted);
}
posted by cerebus19 at 5:41 AM on April 9, 2010

Oy. Forgot to escape things. Let's try that again.


public List<String>(List<String> unsorted) {
   return new TreeList<String>(unsorted);
}
posted by cerebus19 at 5:42 AM on April 9, 2010

Instead, if you do need to do some sort of transform on the object before comparing it:

Collections.sort(sorted, new Comparator<String>(){
  public int compare(String a, String b) { 
    return a.toLowerCase().compareTo(b.toLowerCase());
});

(siskin)

Wait...did Java get anonymous first-class functions when I wasn't looking? I had no idea you could do this! The syntax is clunky, but you just defined a function inline and passed it as an argument, didn't you?
posted by d. z. wang at 8:55 AM on April 9, 2010

d.z. wang, that's not a first-class function. That's an anonymous class. The "new Comparator" makes a new anonymous class implementing the comparator interface. Then he defines the necessary method inside it.

This is used constantly in Java. Especially for trivial event handlers that just call back the the enclosing class.
posted by Netzapper at 10:21 AM on April 9, 2010 [1 favorite]

Response by poster: Thanks for all the help guys. In addition to the Collections.sort approach, wouldn't another (albeit longer) option be to use the compareTo() method?
posted by bookman117 at 1:50 PM on April 9, 2010

Thanks for all the help guys. In addition to the Collections.sort approach, wouldn't another (albeit longer) option be to use the compareTo() method?

Well, it depends on what you mean by "approach".

There are a number of different sorting algorithms. They all have different properties and different computational costs (complexities). The Collections.sort() method uses a slightly modified merge sort.

So, it's certainly possibly to implement one of those algorithms yourself. In my time, I think I've implemented nearly every one on that list. Implementing the "standard" sorts is compsci homework, in fact. [In general, unless you're a brilliant computer scientist, there's no point in trying to invent your own sorting algorithm. You're just going to inadvertently recreate one of the ones listed on that page. I promise.]

All sorting algorithms rely on some sort of a comparison. For numerals (int, long, float, double), this is the obvious less than/greater than comparison. For other objects, we must define our own comparisons. And by "define", I mean not only that we write the code, but that we determine what is meant by "less than" or "greater than".

For strings, we've decided that the most natural order is usually lexicographical order. To compare two strings in lexicographical order, treat each character as a number (A=1, B=2, C=3, etc [not the real numbers we use, btw]). Then, iterate over each character in each string, and compare them; if they're equal, move to the next character, otherwise return the comparison result from the last character. For all phonetic languages I know, this is basically equivalent to alphabetical order--although the order of punctuation is rather arbitrary. For ideographic languages like Chinese, the order is apparently arbitrary.

In Java, the String.compareTo(String) method returns the lexicographical comparison of the two strings. For other objects implementing Comparable, the actual comparison function is determined by the implementers and should be documented in the docs.

So, compareTo() is part of a solution that doesn't use Collections.sort(). However, you still have to do the hard work of implementing a sorting algorithm. Which is why most pros just use the provided Collections.sort()... we implemented merge sort in college, and have no particular desire to do that again if we can avoid it. (Although you often find yourself doing precisely that, since there are numerous systems where the standard library does not include a useful sorting algorithm.)
posted by Netzapper at 7:21 PM on April 9, 2010