Проверка того, находятся ли строки в массиве в алфавитном порядке

Я проверяю, расположены ли строки в моем массиве в алфавитном порядке. Моя программа проверки кода говорит, что мой код не учитывает некоторые случаи, но я действительно не уверен, как это изменить.

РЕДАКТИРОВАТЬ: по-видимому, мой код возвращает «истину» при проверке массива «кошка, обезьяна, собака, зебра», что явно неверно.

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;
}

java alphabetical
person user2577950    schedule 12.07.2013    source источник
comment
Какие случаи? Можешь показать ошибки   -  person Marco Corona    schedule 13.07.2013
comment
Попробуйте написать несколько модульных тестов   -  person Mike Rylander    schedule 13.07.2013
comment
почему вы хотите ЗНАТЬ, если они отсортированы? обычно вам просто нужно СОРТИРОВАТЬ свою коллекцию...   -  person David Hofmann    schedule 13.07.2013
comment
Просто быть чистым. Ваш список должен быть передан этому методу? Или список является глобальной переменной в вашем приложении?   -  person dghalbr    schedule 13.07.2013

Ответы (6)


arrow_upward
7
arrow_downward 

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

Вышеприведенная строка ошибочна. Возвращаемое значение будет положительным и не будет строго равно 1.

Попробуйте изменить на

if (list.get(i).compareTo(list.get(j)) >0)
person Shamim Hafiz    schedule 12.07.2013
comment
Понятно, спасибо за помощь. Должно быть, я неправильно понял Java API. - person user2577950; 13.07.2013

arrow_upward
4
arrow_downward

Я предполагаю, что вы используете переменную экземпляра для сохранения списка String. Попробуйте этот код, где я использую 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);
}
person amatellanes    schedule 12.07.2013
comment
Просто создайте новый список из старого, не нужно добавлять каждый элемент. Список новый список = новый список массивов (старый список); - person Chris Kessel; 13.07.2013
comment
Что еще более важно, это ужасно неэффективный подход. Проверка сортировки должна требовать линейного времени и постоянного дополнительного пространства. Это требует nlog(n) времени и линейного дополнительного пространства. Как уже отмечали другие, код @ user2577950 имеет два недостатка. Неправильное сравнение для вывода compareTo() и отсутствие короткого замыкания при обнаружении несоответствия. - person GinoA; 13.07.2013

arrow_upward
2
arrow_downward

Это намного проще, чем кажется: просто пройдитесь по списку, проверяя, расположены ли соседние элементы в правильном порядке. Если все соседние пары в порядке, то весь список в порядке.

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;
}
person Ermir    schedule 12.07.2013
comment
Как заметил Шамин, лучше было бы написать list.get(i).compareTo(list.get(j)) >0 - person Barranka; 13.07.2013
comment
Еще одно преимущество этого фрагмента кода заключается в том, что он завершает работу в тот момент, когда находит несортированный элемент. Код OP считывает полный список, что может быть ненужным: если одна запись не отсортирована, то и весь список не отсортирован. - person Barranka; 13.07.2013
comment
@Barranka Ответ ОП на самом деле возвращает только сравнение двух последних записей. - person GinoA; 13.07.2013

arrow_upward
0
arrow_downward

compareTo() возвращает положительное значение (не обязательно 1), если строка слева «больше», чем строка справа. Таким образом, вам нужно изменить условие с == 1 на >= 1.

Кроме того, вам не нужен второй цикл (j), который проходит по всем элементам. Вам просто нужно сравнить два последовательных элемента, как показано ниже:

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;
}
person Itay Maman    schedule 12.07.2013

arrow_upward
0
arrow_downward

Использование String.compareTo() — это очень простой способ сделать это.

String.compareTo() возвращает отрицательное число, если строка предшествует аргументу метода, 0, если она совпадает, и положительное число, если строка идет после аргумента метода.

Как вы это сделали:

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

Очень близко, но это должно быть

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

Вы можете использовать это вместе с компаратором для быстрой сортировки или, в вашем случае, проверить, отсортировано ли оно.

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;
}

Или, если вы хотите отсортировать их, это сработает:

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

Источник

Или вернуть true или false

person Stephan    schedule 12.07.2013

arrow_upward
0
arrow_downward

Я знаю, что это вопрос Java, но вот как я очень кратко реализовал это в Kotlin:

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