Collection framwork의 정렬 메소드 탐구

 

 

 

 

1번과 2번의 차이점은 무엇인가? 

List만을 인자로 받는 1번 sort는 list를 오름차순 정렬하여 이를 반환한다.

Comparator를 추가적인 인자로 받는 2번 sort는 정렬기준을 Comparator에 맞춘다. Comparator은 함수형 인터페이스이므로 오름차순과 같은 단순한 정렬기준이 아닌 복잡한 정렬 기준을 사용하고 싶을 때 이를 커스텀하여 정렬 기준을 정의할 수 있다. 

 

 

🔍  sort(List<T> list)

 

 

모르는 개념이 많았다.

• Comparable이란 무엇이고, List의 요소는 왜 Comparable을 상속한 상태여야할까? 
• sort메소드는 또 뭐지? 
• 지금까지 해당 sort메소드의 인자로 리스트를 넘겨줄 때 따로 Comparable을 이용해서 처리해준 기억은 없는데, 그간 어떻게 돌아갔던 것인지 의문점이 들었다.
• 현재 사용하려고하는 sort는 컬렉션 프레임워크에 작성된 메소드이다. 해당 sort 메소드에서는 결국 list.sort()로 이를 처리하니 컬렉션 프레임워크의 sort 메소드는 리스트 자료형을 저격하고 만들어진걸까?

 

 

📌  Comparable interface & Comparotor interface

---

 

 

Comparable 인터페이스를 먼저 알아보기 위해 공식문서를 읽다보니 Comparator 인터페이스와 함께 이해해야 감을 잡을 것 같아 아래 글을 찾아 정리해봤다.

https://st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해

 

 🔼 정리

 

Comparable과 Comparator 모두 함수형 인터페이스이다.

실제 Comparable 인터페이스는 아래와 같다.

public interface Comparable<T> {
   
    public int compareTo(T o);
}

 

 

Comparator 인터페이스는 아래와 같다.

public interface Comparator<T> {
  
    int compare(T o1, T o2);
	
    //이외 메소드 생략
}

 

두 인터페이스는 비슷한 이름, 비슷한 추상메소드를 가지고 있다.(compare, compareTo)

그래서 더욱 헷갈리지만, 사용법이 다르다는 것을 기억 해야한다.

 

먼저 Comparable의 compareTo메소드는 인자로 받는 객체와 자기 자신을 비교하는 용도로 사용한다.

반면에 Comparator의 compare 메소드는 인자로 받는 o1, o2 두 객체를 비교한다.

 

공통점은 비교한 결과에 따라 -1( 또는 음수 ),  0,  1( 또는 양수 )을 반환한다는 점이다.

 

compareTo메소드에서는 본인이 비교할 대상보다 작으면 -1, 같으면 0, 크면 1을 반환한다. 

이때 비교할 대상은 compareTo 메소드의 인자로 받는다.

 

compare 메소드에서는 비교할 두 대상 o1, o2가 있을 때 o1이 o2보다 작으면 -1, 같으면 0, 크면 1을 반환한다.

 

비교 결과 값에 따라 -1(음수), 0, 1(양수)을 반환하는 것은 약속이다. 이미 그렇게 구현되어 있고, 그렇게 구현하면 된다.

 

그렇다면 왜 -1, 0, 1을 반환할까? 

 

이것은 Java에서 정렬을 처리하는 방법과 관련이 있다.  (자세한 설명은 글에 잘 나와있으므로 생략)

Java에서 정렬을 처리할 때는 먼저 두 개의 요소를 비교하여 크고 작음을 판단한다. 이후 해당 과정의 반복을 통해서 정렬이 이루어지게 되는 것이다.

 

이때 비교하고자하는 두 요소가 정량화하지 못하는 객체라면 어떻게 될까?

즉 숫자와 같이 정량화된 수치가 아닌 '객체'를 비교하고자 할 때이다. 

 

이쯤되면 대략 감이 잡힌다. 객체를 비교하고자 할 때는, 우리가 기준을 정해주어야 하겠구나! 하고 말이다.

 

이때 기준을 정해주는 방법이 바로 compareTo, compare 메소드 구현이다.  만약 내가 이러한 기준을 정립해주지 않는다면 정렬이 이루어질 수 없다. 

 

그렇다면 compareTo, compare 메소드에서 비교 결과에 따라 -1, 0, 1을 반환해주는 이유도 짐작해 볼 수 있다. 음수, 0, 양수를 반환함으로써 컬렉션 프레임워크에게 비교 결과를 알려주는 것이다. 두 요소 중에 누가 더 크고 작은지 말이다. 그럼 컬렉션 프레임워크는 이것을 바탕으로 정렬을 수행할 수 있다.

 

Comparable과 Comparator 중에 람다식으로써 활용되는 빈도수가 높은 것은 단연코 Comparator 라고 할 수 있다. Comparable은 자기 자신과 인자로 받은 객체를 비교하는 compareTo메소드를 가지고 있으므로 불편하기 때문이다. (자세한 이유는 참고한 글에 설명되어있으니 글을 참고하면 될 것 같다.)

 

이렇게 Comparable인터페이스와 Comparator 인터페이스에 대해서 이해했다.

 

 

---

 

 

이제 다시 sort 메소드를 바라보면 다음과 같은 궁금증이 남는다.

 

 

 

 

Q1

 정렬 메소드에서
<T extends Comparable<? super T>>는 무엇을 의미할까? 

 

⏩ List의 요소는 Comparable 인터페이스를 구현한,

즉 compareTo메소드를 오버라이딩한 비교 가능한 객체여야한다.

 

다시 말해자면 List의 요소는 비교 가능한 객체여야 한다. ( 당연하다. 정렬을 해야하니까요! )

 

 

Q2

그렇다면 왜, <T extends Comparable<T>> 가 아닌

<T extends Comparable<? super T>>과 같은 제약 조건을 걸었을까?

 

⏩이는 제네릭 클래스의 상속을 보장하기 위한 조건이다.

 

 정렬하려고하는 리스트의 요소들이 직접 compareTo를 구현하지 않고,

부모 클래스의 compareTo를 사용할 수도 있기 때문이다.

 

즉, 내가 구현한 객체 리스트를 정렬하려고 할 때 해당 객체가 상속 관계에 있을 수 있다.

이는 곧 부모의 compareTo를 이용할 수도 있다는 말이다.

 

컬렉션 프레임워크는 이러한 관계까지 폭넓게 수용하기 위해 상속 보장성을 지키도록 설계된 것이다.

 

 

 

 

 

 

참고한 블로그 글_ https://m.blog.naver.com/zxwnstn/221550689930

24-1 Collection Framework2 - 정렬 메소드와 <T extends Compareble<? super T>>

 

🔽 글을 보며 궁금했던 점 정리

 

 1. 나의 경우 T는 String이다. 그럼 String 클래스는 Comparable의 자식클래스여야 말이 된다.

 

⏩ 실제로 구현된 String 클래스에서 Comparable<String>을 구현하고 있는 것을 확인했다. 즉 String은 Comparable을 구현한 클래스가 맞다.

 

 

2. Comparable<T>에서 타입을 지정함으로써 어떤 장점이 있는가

 

⏩  리스트의 타입을 일관되게 유지하도록 한다. 그래야 비교하여 정렬할 수 있다.

 

---

 

 

이제 드디어 알맹이(list.sort(null)) 를 이해해보자.

📌 list.sort()

---

 

List 인터페이스의 sort 메소드를 보면 리스트를 배열로 바꾸어 Arrays의 static 메소드인 sort메소드를 이용하는 모습을 볼 수 있다.

현재 탐구중인 컬렉션 프레임워크의 sort(List<T> list) 메소드에서는 list.sort(null)과 같이 null을 인자로 넘겨주는 것을 상기하며 Arrays 클래스의 sort 메소드를 바라보았다.

 

 

 

 

Array class의 sort 메소드는 Comparator 타입 인자인 c가 null이면 아래와 같은 sort 메소드를 호출한다.

주어진 Comparator가 없으므로 인자로 Comparator를 넘겨주지 않는다.

 

 

 

결과적으로 Comparator가 있으면 ComparableTimSort.sort(), 없으면 TimSort.sort()를 호출하는 것으로 이해했다.

 

---

 

 

ComparableTimSort 클래스에 대해 간단히 알아보기위해  chatgpt씨한테 설명 부탁했다.

chatGPT  👄
ComparableTimSort 클래스는 Java에서 TimSort 알고리즘을 구현한 클래스 중 하나입니다. TimSort는 안정적인 정렬 알고리즘으로, Python의 Timsort에서 영감을 받아 개발되었습니다. TimSort는 주로 Java에서 배열의 정렬에 사용됩니다.
ComparableTimSort 클래스는 객체 배열을 정렬하는데 사용됩니다. 이름에 있는 "Comparable"은 배열의 원소가 Comparable 인터페이스를 구현해야 한다는 것을 의미합니다. 즉, 정렬할 객체는 서로 비교 가능해야 합니다.

 

아래는 TimSort 클래스의 sort 메소드에 대한 chatGPT설명이다.

chatGPT  👄
이 코드는 TimSort 알고리즘을 구현한 메서드입니다. TimSort는 Java의 Arrays.sort() 메서드에서 사용되는 안정적인 정렬 알고리즘 중 하나입니다.
TimSort 알고리즘은 배열을 여러 개의 작은 부분 배열로 분할하고, 각 부분 배열을 정렬한 다음 병합(merge)하여 전체 배열을 정렬합니다. 이 과정에서 배열의 부분 정렬 상태를 활용하여 효율적으로 정렬을 수행합니다.

 

 

자세한건 잘모르겠다.ㅎ 후에 정렬 알고리즘 공부할 때 다시 봐야겠다.

 

 

 

📌 정리

---

• Comparable이란 무엇이고, List의 요소는 왜 Comparable을 상속한 상태여야할까? 
  • Comparable 인터페이스는 compareTo메소드를 이용하여 자기 자신과 인자로 받은 객체를 비교한다.
  • Comparable 를 상속함으로써 비교 가능한 객체를 만들어 정렬하기 위해서이다.
• 지금까지 해당 sort메소드의 인자로 리스트를 넘겨줄 때 따로 Comparable을 이용해서 처리해준 기억은 없는데, 그간 어떻게 돌아갔던 것인지 의문점이 들었다.
  • 지금까지는 String을 요소로 갖고 있는 리스트만을 정렬하였기 때문이다. String은 이미 Comparable인터페이스를 상속하여 구현되어있다.
• 현재 사용하려고하는 sort는 컬렉션 프레임워크에 작성된 메소드이다. 해당 sort 메소드에서는 결국 list.sort()로 이를 처리하니 컬렉션 프레임워크의 sort 메소드는 리스트 자료형을 저격하고 만들어진걸까?
  • 아직 잘모르겄다. 찾아봐야할듯