목록이 Java로 정렬되었는지 확인하는 방법은 무엇입니까?

목록이 Java로 정렬되었는지 확인하는 방법은 무엇입니까?

---

List<T>어디서 T구현 Comparable하고 반환 true하거나 false목록이 정렬되었는지 여부에 따라 방법을 원합니다 .

Java에서 이것을 구현하는 가장 좋은 방법은 무엇입니까? 제네릭과 와일드 카드가 그러한 일을 쉽게 처리 할 수 ​​있다는 것은 분명하지만, 나는 모두 엉키고 있습니다.

목록이 역순인지 확인하는 유사한 방법을 사용하는 것도 좋습니다.

---

Guava 는 멋진 Ordering 클래스 를 통해이 기능을 제공합니다 . An Ordering은 Comparator++입니다. 이 경우를 구현하는 일부 유형의 목록이 있으면 다음과 같이 Comparable작성할 수 있습니다.

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

이것은 Iterable뿐만 아니라 모든 에서 작동하며 다른 비 요소의 앞 또는 뒤에 와야하는지 여부를 지정하여 s를 쉽게 List처리 할 수 ​​있습니다 .nullnull

Ordering.natural().nullsLast().isOrdered(list);

또한 역순과 정상 순서를 확인할 수 있기를 원한다고 언급 했으므로 다음과 같이 수행됩니다.

Ordering.natural().reverse().isOrdered(list);

Java 8 사용자 : Comparators#isInOrder(Iterable)나머지 Ordering은 대부분 쓸모 없기 때문에 대신 동등한 것을 사용하십시오 (클래스 문서에 설명 됨 ).

---

트릭을 수행하는 일반적인 방법은 다음과 같습니다.

public static <T extends Comparable<? super T>>
        boolean isSorted(Iterable<T> iterable) {
    Iterator<T> iter = iterable.iterator();
    if (!iter.hasNext()) {
        return true;
    }
    T t = iter.next();
    while (iter.hasNext()) {
        T t2 = iter.next();
        if (t.compareTo(t2) > 0) {
            return false;
        }
        t = t2;
    }
    return true;
}

---

쉬운:

List tmp = new ArrayList(myList);
Collections.sort(tmp);
boolean sorted = tmp.equals(myList);

또는 (요소가 비교 가능한 경우) :

Object prev;
for( Object elem : myList ) {
    if( prev != null && prev.compareTo(elem) > 0 ) {
        return false;
    }
    prev = elem;
}
return true;

또는 (요소가 비교할 수없는 경우) :

Object prev;
for( Object elem : myList ) {
    if( prev != null && myComparator.compare(prev,elem) > 0 ) {
        return false;
    }
    prev = elem;
}
return true;

null 값을 포함하는 목록에 대한 구현이 실패합니다. 이 경우 적절한 검사를 추가해야합니다.

---

Java 8을 사용하는 경우 스트림이 도움이 될 수 있습니다.

list.stream().sorted().collect(Collectors.toList()).equals(list);

이 코드는 목록을 제자리에서 정렬하고 다른 목록의 요소를 수집 한 다음 초기 목록과 비교합니다. 두 목록이 동일한 위치에 동일한 요소를 포함하면 비교가 성공합니다.

이 방법은 성능이 가장 빠른 솔루션은 아니지만 타사 프레임 워크를 포함하지 않는 구현하기 가장 쉬운 방법입니다.

---

해당 문제에 대한 목록 또는 데이터 구조가 O (n) 시간 만 걸리는 작업인지 확인합니다. Iterator인터페이스를 사용하여 목록을 반복 하고 데이터를 처음부터 끝까지 실행하면 (귀하의 경우 이미 Comparable 유형으로 준비되어 있음) 정렬 여부를 쉽게 찾을 수 있습니다.

---

반복자를 사용하여 List<T>.

public static <T extends Comparable> boolean isSorted(List<T> listOfT) {
    T previous = null;
    for (T t: listOfT) {
        if (previous != null && t.compareTo(previous) < 0) return false;
        previous = t;
    }
    return true;
}

---

private static <T extends Comparable<? super T>> boolean isSorted(List<T> array){
    for (int i = 0; i < array.size()-1; i++) {
        if(array.get(i).compareTo(array.get(i+1))> 0){
            return false;
        }
    }
    return true;
}

zzzzz는 여러분이 무엇을하고 있는지 확실하지 않지만 이것은 간단한 for 루프에서 수행 할 수 있습니다.

---

단위 테스트에 필요한 경우 AssertJ 를 사용할 수 있습니다 . 목록이 정렬되었는지 확인하는 어설 션이 포함되어 있습니다.

List<String> someStrings = ...
assertThat(someStrings).isSorted();

isSortedAccordingTo정렬을 위해 사용자 정의 비교기를 사용하려는 경우 비교기를 사용 하는 대체 방법도 있습니다 .

---

이것은 O (n) 시간이 걸리는 작업입니다 (최악의 경우). 목록이 내림차순으로 정렬되고 목록이 오름차순으로 정렬되는 두 가지 경우를 처리해야합니다.

순서가 유지되는지 확인하면서 각 요소를 다음 요소와 비교해야합니다.

---

이것이 내가 할 일입니다.

public static <T extends Comparable<? super T>> boolean isSorted(List<T> list) {
    if (list.size() != 0) {
        ListIterator<T> it = list.listIterator();
        for (T item = it.next(); it.hasNext(); item = it.next()) {
            if (it.hasPrevious() && it.previous().compareTo(it.next()) > 0) {
                return false;
            }
        }

    }
    return true;
}

---

배열에 대한 간단한 구현 :

public static <T extends Comparable<? super T>> boolean isSorted(T[] a, int start, int end) {
    while (start<end) {
        if (a[start].compareTo(a[start+1])>0) return false;
        start++;
    }
    return true;
}

목록 변환 :

public static <T extends Comparable<? super T>> boolean isSorted(List<T> a) {
    int length=a.size();
    if (length<=1) return true;

    int i=1;
    T previous=a.get(0);
    while (i<length) {
        T current=a.get(i++);
        if (previous.compareTo(current)>0) return false;
        previous=current;
    }
    return true;
}

---

여기에 사용하는 방법 제공 Iterable과를 Comparator.

<T> boolean isSorted(Iterable<? extends T> iterable,
                     Comparator<? super T> comparator) {
    boolean beforeFirst = true;
    T previous = null;
    for (final T current : iterable) {
        if (beforeFirst) {
            beforeFirst = false;
            previous = current;
            continue;
        }
        if (comparator.compare(previous, current) > 0) {
            return false;
        }
        previous = current;
    }
    return true;
}

및 주문 을위한 Iterableof Comparable및 플래그에 대한 메소드 .

<T extends Comparable<? super T>> boolean isSorted(
        Iterable<? extends T> iterable, boolean natural) {
    return isSorted(iterable, natural ? naturalOrder() : reverseOrder());
}

---

Java 8 스트림 사용 :

boolean isSorted = IntStream.range(1, list.size())
        .map(index -> list.get(index - 1).compareTo(list.get(index)))
        .allMatch(order -> order <= 0);

This also works for empty lists. It is however only efficient for lists that also implement the RandomAccess marker interface (e.g., ArrayList).

If you do not have access to the stream's underlying collection, the following ugly hack can be used:

Stream<T> stream = ...
Comparator<? super T> comparator = ...
boolean isSorted = new AtomicInteger(0) {{
    stream.sequential()
          .reduce((left, right) -> {
               getAndUpdate(order -> (order <= 0) ? comparator.compare(left, right) : order);
               return right;
          });
}}.get() <= 0;

ReferenceURL : https://stackoverflow.com/questions/3047051/how-to-determine-if-a-list-is-sorted-in-java