«Проверка сортировки массива в Java»

«1. Обзор

В этом руководстве мы рассмотрим различные способы проверки того, отсортирован ли массив.

Прежде чем начать, было бы интересно проверить, как сортировать массивы в Java.

2. Цикл

Один из способов проверки — цикл for. Мы можем перебирать все значения массива одно за другим.

Давайте посмотрим, как это сделать.

2.1. Примитивный массив

Проще говоря, мы будем перебирать все позиции, кроме последней. Это потому, что мы собираемся сравнить одну позицию со следующей.

Если какие-то из них не отсортированы, метод вернет false. Если ни одно из сравнений не возвращает false, это означает, что массив отсортирован:

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

2.2. Объекты, реализующие Comparable

Мы можем сделать нечто подобное с объектами, реализующими Comparable. Вместо знака «больше» мы будем использовать compareTo:

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

2.3. Объекты, которые не реализуют Comparable

Но что, если наши объекты не реализуют Comparable? В этом случае мы можем вместо этого создать Comparator.

В этом примере мы будем использовать объект Employee. Это простой POJO с тремя полями:

public class Employee implements Serializable {
    private int id;
    private String name;
    private int age;

    // getters and setters
}

Затем нам нужно выбрать, по какому полю мы хотим упорядочить. Здесь давайте упорядочим по полю возраста:

Comparator<Employee> byAge = Comparator.comparingInt(Employee::getAge);

И затем мы можем изменить наш метод, чтобы он также принимал Comparator:

boolean isSorted(Object[] array, Comparator comparator) {
    for (int i = 0; i < array.length - 1; ++i) {
        if (comparator.compare(array[i], (array[i + 1])) > 0)
            return false;
    }

    return true;
}

3. Рекурсивно

Вместо этого мы можем, конечно, использовать рекурсию . Идея здесь в том, что мы проверим две позиции в массиве, а затем рекурсивно проверим каждую позицию.

3.1. Примитивный массив

В этом методе мы проверяем две последние позиции. Если они отсортированы, мы снова вызовем метод, но с предыдущей позицией. Если одна из этих позиций не отсортирована, метод вернет false:

boolean isSorted(int[] array, int length) {
    if (array == null || length < 2) 
        return true; 
    if (array[length - 2] > array[length - 1])
        return false;
    return isSorted(array, length - 1);
}

3.2. Объекты, реализующие Comparable

Теперь давайте снова посмотрим на объекты, реализующие Comparable. Мы увидим, что тот же подход с compareTo будет работать:

boolean isSorted(Comparable[] array, int length) {
    if (array == null || length < 2) 
        return true; 
    if (array[length - 2].compareTo(array[length - 1]) > 0)
        return false;
    return isSorted(array, length - 1);
}

3.3. Объекты, которые не реализуют Comparable

Недавно давайте снова попробуем наш объект Employee, добавив параметр Comparator:

boolean isSorted(Object[] array, Comparator comparator, int length) {
    if (array == null || length < 2)
        return true;
    if (comparator.compare(array[length - 2], array[length - 1]) > 0)
        return false;
    return isSorted(array, comparator, length - 1);
}

4. Заключение

В этом руководстве мы увидели, как проверить, является ли массив сортируется или нет. Мы видели как итеративные, так и рекурсивные решения.

Мы рекомендуем использовать циклическое решение. Он чище и легче читается.

Как обычно, исходный код этого руководства можно найти на GitHub.