[JAVA] 리스트(List) 정렬: Collections.sort() 코드를 뜯어보았다, Comparable

컬렉션 프레임워크의 List를 정렬할 때 사용되는 Collections.sort()에 대한 포스팅이다!

 

 

👍🏻 요약

 

Collections.sort(List이름): 기본 정렬 기준으로 정렬한다.
Collections.sort(List이름, Comparator): Comparator 인터페이스를 구현한 인스턴스에서 지정한대로 정렬한다.

 

아래는 예시 코드이다.

 

List<String> animals = new ArrayList<>(List.of("깃짱", "오잉", "이리내", "허브", "주노", "제나"));
Collections.sort(animals);
System.out.println(animals); // [깃짱, 오잉, 이리내, 제나, 주노, 허브]
Collections.sort(animals, (o1, o2) -> o1.charAt(1) - o2.charAt(1));
System.out.println(animals); // [제나, 주노, 이리내, 허브, 오잉, 깃짱]

 

---

 

Collections 클래스에 들어가 보면, 정렬과 관련된 메서드가 두 개 정의되어 있다. 둘 다 이름은 sort이고, 오버로딩되어 파라미터를 두 종류로 받고 있다.

 

 

💋 Collections 클래스의 Collections.sort()

 

T extends Comparable 이런건 제네릭에 대해 공부를 해야 알 수 있다. 우리가 주목할 것은 파라미터로 list를 받는다는 것이다. 위에 겁나 길어서 글 접고싶은 영어 설명을 해석해보면, 특정 리스트를 오름차순으로 정렬하는데, 기본으로 제공되는 Comparable의 순서에 따라서 정렬한다. 리스트에 들어있는 모든 원소들은 Comparable 인터페이스를 구현하고 있어야 한다. 또 리스트 내 원소들은 서로 비교할 수 있어야 하는데, e1.compareTo(e2)를 호출했을 때 ClassCastException이 발생하지 않아야 한다. 

 

Comparator가 뭔지, 알아봐야 할 것 같다.

 

/**
 * Sorts the specified list into ascending order, according to the
 * {@linkplain Comparable natural ordering} of its elements.
 * All elements in the list must implement the {@link Comparable}
 * interface.  Furthermore, all elements in the list must be
 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)}
 * must not throw a {@code ClassCastException} for any elements
 * {@code e1} and {@code e2} in the list).
 *
 * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 * not be reordered as a result of the sort.
 *
 * <p>The specified list must be modifiable, but need not be resizable.
 *
 * @implNote
 * This implementation defers to the {@link List#sort(Comparator)}
 * method using the specified list and a {@code null} comparator.
 *
 * @param  <T> the class of the objects in the list
 * @param  list the list to be sorted.
 * @throws ClassCastException if the list contains elements that are not
 *         <i>mutually comparable</i> (for example, strings and integers).
 * @throws UnsupportedOperationException if the specified list's
 *         list-iterator does not support the {@code set} operation.
 * @throws IllegalArgumentException (optional) if the implementation
 *         detects that the natural ordering of the list elements is
 *         found to violate the {@link Comparable} contract
 * @see List#sort(Comparator)
 */
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

 

list.sort(null)를 호출하고 있다. 이건 잠시후 뜯어보겠다.

 

위에서 본 코드 바로 아래에 적혀있는 오버로딩된 메서드이다. 파라미터를 하나 더 받는데, Comparator 인터페이스의 구현체를 받고 있다. 

 

/**
 * Sorts the specified list according to the order induced by the
 * specified comparator.  All elements in the list must be <i>mutually
 * comparable</i> using the specified comparator (that is,
 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
 * for any elements {@code e1} and {@code e2} in the list).
 *
 * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will
 * not be reordered as a result of the sort.
 *
 * <p>The specified list must be modifiable, but need not be resizable.
 *
 * @implNote
 * This implementation defers to the {@link List#sort(Comparator)}
 * method using the specified list and comparator.
 *
 * @param  <T> the class of the objects in the list
 * @param  list the list to be sorted.
 * @param  c the comparator to determine the order of the list.  A
 *        {@code null} value indicates that the elements' <i>natural
 *        ordering</i> should be used.
 * @throws ClassCastException if the list contains elements that are not
 *         <i>mutually comparable</i> using the specified comparator.
 * @throws UnsupportedOperationException if the specified list's
 *         list-iterator does not support the {@code set} operation.
 * @throws IllegalArgumentException (optional) if the comparator is
 *         found to violate the {@link Comparator} contract
 * @see List#sort(Comparator)
 */
@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

 

그리고 그 구현체를 list.sort()의 파라미터로 보내고 있다. 뭐부터 뜯어볼까?

 

💋 List 클래스의 list.sort()

 

설명 겁나 길다 읽다 지칠듯 요약해보겠음

 

이 리스트를 지정된 Comparator에 따라서 정렬한다. 아까처럼 모든 원소는 서로 비교 가능해야 하고, Comparator 자리에 null이 들어오면 기본 정렬 기준을 따른다. 들어오는 리스트는 수정 가능(modifiable)해야 한다.

대강 요정도 알면 될 것 같다. 

 

/**
 * Sorts this list according to the order induced by the specified
 * {@link Comparator}.  The sort is <i>stable</i>: this method must not
 * reorder equal elements.
 *
 * <p>All elements in this list must be <i>mutually comparable</i> using the
 * specified comparator (that is, {@code c.compare(e1, e2)} must not throw
 * a {@code ClassCastException} for any elements {@code e1} and {@code e2}
 * in the list).
 *
 * <p>If the specified comparator is {@code null} then all elements in this
 * list must implement the {@link Comparable} interface and the elements'
 * {@linkplain Comparable natural ordering} should be used.
 *
 * <p>This list must be modifiable, but need not be resizable.
 *
 * @implSpec
 * The default implementation obtains an array containing all elements in
 * this list, sorts the array, and iterates over this list resetting each
 * element from the corresponding position in the array. (This avoids the
 * n<sup>2</sup> log(n) performance that would result from attempting
 * to sort a linked list in place.)
 *
 * @implNote
 * This implementation is a stable, adaptive, iterative mergesort that
 * requires far fewer than n lg(n) comparisons when the input array is
 * partially sorted, while offering the performance of a traditional
 * mergesort when the input array is randomly ordered.  If the input array
 * is nearly sorted, the implementation requires approximately n
 * comparisons.  Temporary storage requirements vary from a small constant
 * for nearly sorted input arrays to n/2 object references for randomly
 * ordered input arrays.
 *
 * <p>The implementation takes equal advantage of ascending and
 * descending order in its input array, and can take advantage of
 * ascending and descending order in different parts of the same
 * input array.  It is well-suited to merging two or more sorted arrays:
 * simply concatenate the arrays and sort the resulting array.
 *
 * <p>The implementation was adapted from Tim Peters's list sort for Python
 * (
 * TimSort</a>).  It uses techniques from Peter McIlroy's "Optimistic
 * Sorting and Information Theoretic Complexity", in Proceedings of the
 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 * January 1993.
 *
 * @param c the {@code Comparator} used to compare list elements.
 *          A {@code null} value indicates that the elements'
 *          {@linkplain Comparable natural ordering} should be used
 * @throws ClassCastException if the list contains elements that are not
 *         <i>mutually comparable</i> using the specified comparator
 * @throws UnsupportedOperationException if the list's list-iterator does
 *         not support the {@code set} operation
 * @throws IllegalArgumentException
 *         (<a href="Collection.html#optional-restrictions">optional</a>)
 *         if the comparator is found to violate the {@link Comparator}
 *         contract
 * @since 1.8
 */
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

 

이제 그럼 Comparator만 알게 되면 정렬은 정복하는건가?

 

 

💋 Comparator 인터페이스

 

@FunctionalInterface
public interface Comparator<T> {

    int compare(T o1, T o2);
}

 

사실 위에 설명도 많고, 밑에 default 메서드도 정말 많다. 근데 이렇게 퍼온 이유는 Comparator 인터페이스가 함수형 인터페이스라는 것을 부각하기 위해서이다. 함수형 인터페이스에 대해서는 아래 링크에 자세히 설명해 놓았다.

 

 

암튼 돌아와서 Comparator 인터페이스를 구현하려면 compare 메서드를 만들어 놔야 하는데, o1와 o2 두 객체 또는 값이 들어오게 되었을 때 둘을 비교하는 메서드를 작성하면 된다. 

 

설명을 이제서야 보여주자면 아래와 같다.

 

요약해보면, 두 요소를 비교해서 o1이 더 작으면 음수, o1과 o2가 같으면 0, o1이 더 크면 양수를 반환하는 메서드를 만들어야 한다. 밑에는 더 꼼꼼히 제약조건에 대해 다루고 있는데, 당장 사용하는데 어려움은 없을 것 같다. 

 

 

내가 리스트에 넣은 원소들을 갖고 어떻게 비교하고 싶은지 생각해서 만들면 되는 것이다. 

 

 

💋 내가 만든 Comparator 

 

Comparator는 함수형 인터페이스니깐, 람다식으로 간단히 구현해 봤다. 

 

첫 번째 sort에서는 두 번째 파라미터로 아무것도 넣지 않자 기본 정렬 기준인 가나다순으로 내 리스트를 정렬해 줬다. 

 

두 번째 sort에서는 요상하긴 하지만, 각 닉네임의 두 번째 글자를 기준으로 charAt()을 통해서 char을 뽑아냈고 이 두 개를 서로 빼서 만일 가나다순에서 o1의 두 번째 글자가 더 앞쪽이라면 양수가 나오고 뒤쪽이라면 음수가 나오게 된다. 그래서 이번에 두 번째 글자를 기준으로 보면 나 노 리 브 잉 짱 이다. 잘 된듯!

 

public class ComparatorStudy {

    public static void main(String[] args) {
        List<String> animals = new ArrayList<>(List.of("깃짱", "오잉", "이리내", "허브", "주노", "제나"));
        Collections.sort(animals);
        System.out.println(animals); // [깃짱, 오잉, 이리내, 제나, 주노, 허브]
        Collections.sort(animals, (o1, o2) -> o1.charAt(1) - o2.charAt(1));
        System.out.println(animals); // [제나, 주노, 이리내, 허브, 오잉, 깃짱]
    }
}

 

 

 

💋 이미 만들어진 Comparator 

 

위에서 예시로 들어준 o1.charAt(1) - o2.charAt(1)는 결국 두 int를 비교하는 메서드이다.

 

Collections.sort(animals, (o1, o2) -> o1.charAt(1) - o2.charAt(1));

 

누가 잘 만들어놨겠지?

 

 

역시나...! 있다!

이렇게 바꿀 수 있다.

 

Collections.sort(animals, Comparator.comparingInt(o -> o.charAt(1)));

 

더 좋은거 없나???

곧바로 이렇게 편리하게 Comparator를 만들 수 있게 메서드가 또 이미 있다.

 

 Comparator<String> cmp = Comparator.comparingInt(String::length)          
 			.thenComparing(String.CASE_INSENSITIVE_ORDER);

 

thenComparing은 원하는 기준을 쓰고, 그 다음 기준으로 올 것을 뒤에 적어주면 된다. 

 

이외에도 많은 메서드가 정의되어 있어서 미리 만들어놓은 게 많은데, 천천히 하나씩 잘 써봐야겠다. 

 

정렬 잘 하자!