[영상후기] [자바의 정석 - 기초편] ch11-30~33 Comparator와 Comparable

Comparator와 Comparable

• 객체 정렬에 필요한 메서드(정렬기준 제공)을 정의한 인터페이스
  • Comparable : 기본 정렬기준을 구현하는데 사용(default)
  • Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용

public interface Comparator {
	// 결과 : 0(같음), 양수(왼쪽이 큰 것), 음수(오른쪽이 큰 것)
	int compare(Object o1, Object o2); // o1, o2 두 객체를 비교
    boolean equals(Object obj); // equals를 오버라이딩 하라는 뜻
 }
 
 public interface Comparable {
 	int compareTo (Object o); // 주어진 객체를 자신(this)과 비교
  }

• 정렬 : 두 대상을 비교하여 자리를 바꾸는 것 -> 반복하는 것
  • compare : 두 객체를 비교
  • compareTo : 자신과 비교
• Integer Class 예제

public final class Integer extends Number implements Comparable {
	...
    public int compareTo(Integer anotherInteger) {
    	int v1 = this.value;
        int v2 = anotherInteger.value;
        // 같으면 0, 오른쪽 값이 크면 -1, 작으면 1을 반환
        return (v1 < v2 ? -1 : (v1 == v2 ? 0 : 1));
    }
    ...
}

• Integer Class에서 두 숫자의 차이로 어느쪽이 큰지 비교할 수 있지만, 삼항연산자를 사용한 이유

  • Integer 32bit 연산 시 32bit 모두 사용하여 뺄셈 이용해야 함
  • 하지만 삼항연산자를 사용할 경우 앞에서부터 비교하다가 차이나면 바로 반환가능
    • 32bit를 모두 사용하지 않아도 되어 성능 약간 증가

• compare()와 compareTo()는 두 객체의 비교결과를 반환하도록 작성

  • 같으면 0, 오른쪽이 크면 음수(-), 작으면 양수(+)
    • 오름차순정렬 되는 case : 7 5 -> 5 7
      • 왼쪽이 더 큰 상태(7 > 5)라 결과가 +임. 순서 맞추기 위해 좌우를 바꿔줘야 함
      • 비교 결과가 양수일 때 오름 차순 정렬
    • 내림차순정렬 되는 case : 5 7 -> 7 5
      • 오른쪽이 더 큰 상태(5 < 7)라 결과가 -임. 순서 맞추기 위해 좌우를 바꿔줘야 함
      • 비교 결과가 음수일 때 내림차순 정렬

---

예제

• 정렬 : 대상, 기준 필요
  • 정렬 기준을 명시하지 않으면 기본 정렬기준 사용(Comparable)
  • 별도로 명시해주기 위해선 Comparator 인터페이스를 구현한 기준을 넣어줘야 함
    • 아래 코드에서 2번쩨 매개변수 c

static void sort(Object[] a) // 객체 배열에 저장된 객체가 구현한 Comparable에 의한 정렬
static void sort(Object[] a, Comparator c) // 지정한 Comparator에 의한 정렬

• 정렬 예시 : String 문자열 배열 각각 기준대로 정렬하기

import java.util.*;

class Ex11_7 {
	public static void main(String[] args) {
    	String[] strArr = {"cat", "Dog", "lion", "tiger"};
        
        Arrays.sort(strArr); // Case 1 : String의 Comparable 구현에 의한 정렬 (기본 사전순 정렬 구현되어 있음)
        Arrays.sort(strArr, String.CASE_INSENSITIVE_ORDER); // Case 2 : 대소문자 구분 안함
        Arrays.sort(strArr, new Descending()); // Case 3 : 역순 정렬
        }
   }
   
class Descending implements Comparator {
	public int compare(Object o1, Object o2) {
    	if( o1 instanceof Comparable && o2 instanceof Comparable) {
        	Comparable c1 = (Comparable)o1;
            Comparable c2 = (Comparable)o2;
            return c1.comparableTo(c2) * -1; // -1을 곱해서 기본 정렬방식의 역으로 변경 
            // 또는 C2.comparableTo(c1)으로 순서를 바꿔도 된다
    }
}

• Case 1 : 기본 정렬 기준 활용
  • 객체 배열에 저장된 객체가 구현한 Comparable에 의한 정렬
  • Arrays.sort(strArr);
    • String은 내부적으로 Comparable 구현되어 있어 기본 정렬기준 따름
      • 기본 사전순 정렬로 구현되어 있음
• Case 2 : 지정한 Comparator에 의한 정렬
  • String.CASE_INSENSITIVE_ORDER : 대소문자 구분 안하는 정렬 기준
    • 내부적으로 Comparator를 구현해둠
• Case 3 : 역순 정렬
  • 기본 정렬(사전순)의 반대
    • 기본 정렬 기분 : c1.compareTo(c2)
    • 반대 : c2.compareTo(c1) or c1.compareTo(c2) * -1
  • 정렬 기준을 준다는 것 : Comparator를 구현한 것이어야 함

---

결론

• 불변 부분은 나두고 가변 부분만 제시
  • 불변 : 두 대상을 비교하고 자리 바꿈 반복 (불변)
    • 버블 정렬 : 두개 비교, 자리 바꿈 (불변)
      • 비교하는 정렬 기준만 변경 가능 (arr[i] > arr[i+1] or arr[i] < arr[i+1] or 나이순, ...)
  • 가변 : 정렬 기준(오름차순, 내림차순, ...)
• 정렬 알고리즘은 이미 잘 작성되어 있고 비교 기준을 주기만 하면 됨
  • ex) Arrays.sort() => 배열, 정렬기준 주면 됨
    • reverseOrder()로 내림차순 지정 가능 (없으면 오름차순)
    • Comparator의 정렬 기준의 반환값은 그냥 대소 결과만 반환하여 그 결과를 가지고 기본 오름차순으로 정렬(reverseOrder()를 사용하면 내림차순)

---

역순 정렬 방법 GPT 확인 사항

• 출처 : 뤼튼

---

람다식 정렬 방식 GPT 확인 사항

• o1, o2 -> o1 - o2 이게 왜 도대체 오름차순인지, o2-o1이 도대체 왜 내림차순인지 정말 모르겠어서 뤼튼과 정말 토론..
• 결론 : 람다식 뒤에 나오는 순서에 따라 큰 수를 뒤에둘지(오름차순) 앞에둘지(내림차순) 나뉨
  • o1-o2 : 정렬 알고리즘은 o1-o2가 양수라면(o1이 더 큰것) 큰 수를 뒤로 보낸다고 판단
    • 오름차순
  • o2-o1 : o2 - o1 이 양수라면(o2가 더 큰것), 큰 수를 앞에 둔다고 판단
    • 내림차순
• 출처 : 뤼튼

---

CompareTo 각 Case별 찐막 정리

• 양수 반환 : 첫 번째 인자가 두 번째 인자보다 큰 것으로 인식 -> 첫 번째가 뒤에 나옴
• 음수 반환 : 첫 번째 인자가 두 번째 인자보다 작은 것으로 인식 -> 첫 번째가 앞에 나옴

// o1 : 2 , o2 : 6 => o2 - o1 > 0 -> 첫 번째 인자가 큰 것으로 인식되어 첫번째 수인 o1이 뒤에 나옴
// 따라서 [6, 2] 순서로 정렬됨
list.stream()
.sort(o1, o2 -> o2 - o1)
...

			// 음악 2개 이상이라면 재생 횟수가 많은 순으로 정렬 후 삽입, 같을 경우 인덱스 낮은 순
			List<Integer> sortedList = list.stream()
				.sorted((o1, o2) -> {
						int play1 = plays[o1];
						int play2 = plays[o2];
						if (play1 == play2) {
							// 재생 횟수가 같은 경우, 인덱스가 낮은 노래가 먼저 오도록 변경
							return o1 - o2;
						} else if (play1 < play2) {
							// 양수 반환 : 첫 번째 인자가 두번째 인자보다 큼을 의미(왼 > 오)
							// 항상 큰것이 뒤로 가게 정렬되기 때문에 왼쪽꺼가 뒤로 가짐
							// Comparator : 양수일 경우 첫번째가 뒤에 나옴
							return 1;
						}
						// play1 > play2
						else {
							// 음수 반환 : 첫 번째 인자가 두번째 인자보다 작음을 의미(왼 < 오)
							// 첫번째 인자가 항상 작으니 첫번째꺼가 앞에옴
							// Comparator : 음수일 경우 첫번째가 앞에 나옴
							return -1;
						}
					}
				)
				.collect(Collectors.toList());