Checking if Strings in an Array are in Alphabetical Order

Question

I'm checking if the strings in my array are arranged in alphabetical order. My codechecker is saying that my code fails to account for some cases, but I'm really not sure how to change it.

EDIT: Apparently my code returns "true" when checking the array "cat ape dog zebra", which is clearly false.

public boolean isSorted()
{
    boolean sorted = true;                          
    for(int i = 0; i < list.size(); i++)
    {
        for(int j = i+1; j < list.size(); j++) 
        {
            if (list.get(i).compareTo(list.get(j)) == 1)
            {
                sorted = false;
            }  
        }  
    }                
    return sorted;
}

why do you want KNOW if they are sorted? normally you just need to SORT your collection... — David Hofmann, Jul 12 '13 at 21:21
Just to be clear. Is your list supposed to be passed to this method? Or is list a global variable in your application? — dghalbr, Jul 12 '13 at 21:22

score 7 · Answer 1 · answered Jul 12 '13 at 21:24

7

if (list.get(i).compareTo(list.get(j)) == 1)

The above line is erroneous. The returned value would be positive and not strictly equal to 1.

Try changing to

if (list.get(i).compareTo(list.get(j)) >0)

answered Jul 12 '13 at 21:24

Shamim Hafiz - MSFT

21,454
43
116
176

1

I see, thanks for your help. I must have misread the Java API. – user2577950 Jul 12 '13 at 21:25

amatellanes · Answer 2 · 2013-07-12T22:36:23.967

4

I guess you're using a instance variable to save a list of String. Try this code where I use Collections.sort():

public boolean isSorted() {

    // Copies all of the elements from one list into another.
    List<String> listSorted = new ArrayList<String>(list);

    // Sorts the new list.
    Collections.sort(listSorted);

    // Check if both of list are equals.
    return listSorted.equals(list);
}

edited Jul 12 '13 at 22:36

answered Jul 12 '13 at 21:36

amatellanes

3,645
2
17
19

1

Just create a new list from the old, no need to walk through adding each element. List newList = new ArrayList(oldList); – Chris Kessel Jul 12 '13 at 21:46
More importantly, this is a horribly inefficient approach. Checking sort should require linear time and constant additional space. This requires nlog(n) time and linear additional space. As others have pointed out, @user2577950's code has two flaws. The incorrect comparison for compareTo()'s output and not short-circuiting when finding a mismatch. – GinoA Jul 12 '13 at 22:01

score 2 · Answer 3 · answered Jul 12 '13 at 21:26

2

It's far easier than it looks: just iterate over the list, checking if adjacent elements are in the right order. If all adjacent pairs are in order, then the whole list is.

public boolean isSorted()
{
    for(int a=0;a<list.size()-1;a++)
    {
        if(list.get(a).compareTo(list.get(a+1))>0)
        {
            return false;
        }
    }
    return true;
}

answered Jul 12 '13 at 21:26

Ermir

1,391
11
25

As noted by Shamin, would be better to write `list.get(i).compareTo(list.get(j)) >0` – Barranka Jul 12 '13 at 21:27
Another advantage of this piece of code is that it exits in the moment it finds an unsorted element. The OP code reads the full list, which can be unnecesary: If one entry is unsorted, then the full list is unsorted – Barranka Jul 12 '13 at 21:30
@Barranka The OP's answer actually only returns the comparison of the last two entries. – GinoA Jul 12 '13 at 22:03

score 0 · Answer 4 · edited May 23 '17 at 12:00

Using String.compareTo() is a very easy way to do it.

String.compareTo() returns a negative number if the string precedes the argument of the method, 0 if it is the same, and a positive number if the string comes after the argument of the method

The way you did it:

if (list.get(i).compareTo(list.get(j)) == 1)

Is very close, but it should be

if (list.get(i).compareTo(list.get(j)) > 0)

You could use that alongside of a comparator to quickly sort, or in your case check to see if it is sorted

boolean isSorted(String[] words) {

    for (int i = 0; i < words.length()-1; i++) {
        if (words[i].compareTo(words[i+1] >= 0) {
            return false;
        }
    }
    return true;
}

Or if you wanted to sort them, this would work:

Collections.sort(fooList,
             new Comparator<String>()
             {
                 public int compare(String s1, String s2)
                 {
                     return s1.compareTo(s2);
                 }        
             });

Source

Or to return true or false

score 0 · Answer 5 · answered Jul 12 '13 at 21:29

compareTo() returns a positive value (not necessarily 1) if the string on the left-hand-side is "greater" than the one on the right. Thus, you need to change the condition from == 1 to >= 1.

Also, you don't need a second loop (j) that runs over all elements. You just need to compare two consecutive elements, as follows:

public boolean isSorted()  {
    for(int i = 1; i < list.size(); i++) 
        if (list.get(i).compareTo(list.get(i - 1)) >= 1) 
          return false;
    return true;
}

score 0 · Answer 6 · answered Jul 24 '18 at 01:24

0

I know it's a Java question, but here's how I ended up implementing this in Kotlin very succinctly:

myList.zipWithNext { a, b ->
    if (a > b) {
         fail("Expected a sorted list, but $a > $b")
    }
}

answered Jul 24 '18 at 01:24

Rik

790
8
11

Checking if Strings in an Array are in Alphabetical Order

6 Answers6