7

I have an ArrayList called account which contains Strings. I'm trying to write a method that checks if they are in order and returns true or false based on whether they are in order or not.

How would you go about this? I've already tried checking the initial chracter with a for-loop but it went terribly wrong. I created a new ArrayList and set it equal to the original, then sorted it and compared them but since they contained the same data it always came back true.

Just an extra quick question, since I'm doing this for Strings, how would you check if some numbers were in ascending/descending order? Throught the same principal?

Thankyou!

mino
  • 6,978
  • 21
  • 62
  • 75
  • http://stackoverflow.com/questions/3047051/how-to-determine-if-a-list-is-sorted-in-java combined with the javadoc of the `String#compareTo(String)` method should get you going – Robin Jan 01 '12 at 21:11
  • 1
    to any: using String.compareTo doesn't mean *alphabetical* order. either compareToIgnoreCase or some version of `java.text.Collator` is needed – bestsss Jan 01 '12 at 21:25
  • Correct answer depends whether you really have to "write a method" or "find out whether list is sorted". In the second case you're best without actually writing a method and using external library like Guava's Ordering class (see my answer for details). Just not to be another author of a wheel :) – Piotr Findeisen Jan 01 '12 at 21:43

6 Answers6

13

Try this (assuming you want to compare the strings using their natural ordering, of course):

String previous = ""; // empty string: guaranteed to be less than or equal to any other

for (final String current: thelist) {
    if (current.compareTo(previous) < 0)
        return false;
    previous = current;
}

return true;

This is due to the fact that String implements Comparable<String>, and the comparison will be done using the strings' natural ordering.

fge
  • 119,121
  • 33
  • 254
  • 329
  • @dantuch, lots of final reminds me overusing const in c++, sometime just makes pain to code (at least in java it can't be enforced) – bestsss Jan 01 '12 at 21:30
  • @bestsss that's a matter of coding style, as always – fge Jan 01 '12 at 21:32
  • @bestsss doesn't this loop looks better with that final? After first 5 chars you already know that it's meant to not change any element of that list, so it only reads it. That's nice. – dantuch Jan 01 '12 at 21:33
  • 2
    @dantuch, final does not mean *to not change any element of that list*, though. it means the local variable reference won't change. changing elements content in the list would require immutable class (String is one, indeed) and it has nothing to do w/ `final` here. `for in` ensures no modifications, it's sorta weird it's applicable to `iterator` since it may not use `remove()`, but that's another odd point (xforming iterator to `Enumeration` that was basically deprecated) – bestsss Jan 01 '12 at 21:43
  • @bestsss: a foreach loop indeed ensures that, however nothing prevents you from reusing the reference -- a final prevents this – fge Jan 01 '12 at 21:46
  • If you prefer read-to-use method, use Guava's `Ordering` class. See my answer for details. – Piotr Findeisen Jan 01 '12 at 22:16
  • @fge, in around 20+ year i do not recall a single time mistakenly reusing local reference/variable even if i was exceptionally drunk. probably it can happen but i still deem it exceptionally unlikely. – bestsss Jan 02 '12 at 00:19
  • strange then the const is a keyword in java (though not used). – Kango_V Nov 23 '12 at 18:04
6

If you don't mind using external library (Guava) Ordering will do:

boolean isSorted = Ordering.natural().isOrdered(list);

This will do for String and other Comparables. If you are check ordering of some custom type, use any of the static factory methods in the Ordering class or subclass it.

Edit for case-insensitive ordering use:

boolean isSorted = Ordering.from(String.CASE_INSENSITIVE_ORDER).isOrdered(list);
Piotr Findeisen
  • 19,480
  • 2
  • 52
  • 82
  • 1
    @bestsss right, but looking at the accepted answer, String's natural ordering was actually meant by OP. I'm adding a note to my answer anyway. – Piotr Findeisen Jan 02 '12 at 10:55
2

I think a for loop would be suitable for this. The approach I would take would be to check each word against the previous and see if they are in the correct alphabetical ordering. Best case this is O(2) for determining that the list is out of order, worst case O(n) for telling you that the list is in order.

Edit: fge's answer above outlines the code for approach described.

Finbarr
  • 31,350
  • 13
  • 63
  • 94
  • +1 for appropriate running-time cases. I suggest the use of the `compareTo()` method of the String class to do this. This works the same way for number classes such as `Integer`,`Long`,`Double`... et cetera. – Zéychin Jan 01 '12 at 21:12
1

Use the sort method of Collection class : 

List<String> list = new ArrayList<String>();
//Add Elements
Collections.sort(list);

Sorts the specified list into ascending order, according to the natural ordering of its elements.

aleroot
  • 71,077
  • 30
  • 176
  • 213
0

Just use a loop and check if they are in order:

boolean isSorted = true;
for(int i = 0; i < list.size() - 1; i++) {
   // current String is > than the next one (if there are equal list is still sorted)
   if(list.get(i).compareToIgnoreCase(list.get(i + 1)) > 0) { 
       isSorted = false;
       break;
   }
}
dantuch
  • 9,123
  • 6
  • 45
  • 68
Tudor
  • 61,523
  • 12
  • 102
  • 142
0
ArrayList<String> initial = // smth
ArrayList<String> copy = // copy initial list here
Collections.sort(initial);
return initial.equals(copy);
mishadoff
  • 10,719
  • 2
  • 33
  • 55
  • asume that you have `list` with 9 999 999 strings, each of them is long, and after first few elements you can tell that it's not sorted with just simple `if` inside loop. Wouldn't it go faster? ;) – dantuch Jan 01 '12 at 21:26
  • It's simple solution not fast. All depends on your needs. – mishadoff Jan 02 '12 at 11:18