[Java] Comparable과 Comparator로 정렬 이해하기

Java

[Java] Comparable과 Comparator로 정렬 이해하기

jundyu 2024. 10. 13. 17:27

들어가며

알고리즘 유형 중 정렬에 대해 깊게 공부하던 중 다양한 정렬 방식에 대한 정리가 필요하다고 느꼈습니다. Arrays.sort 메서드로 단순히 오름차순으로 정렬하는 것을 넘어 배열이나 문자열의 특정 조건으로 정렬할 필요가 생겼습니다. Comparable과 Comparator가 무엇인건지. 그리고 이 인터페이스로 어떻게 정렬을 구현하는건지에 대한 명확한 정리가 필요해서 이 글을 작성하게 되었습니다.

Comparable과 Comparator

Comparable과 Comparator는 둘 다 자바에서 객체를 정렬할 때 사용하는 인터페이스입니다. 하지만 두 인터페이스의 정렬 방식에는 미묘한 차이가 있습니다.

Comparable
객체 자체에 자연스러운 정렬 순서를 정의할 수 있도록 설계된 인터페이스입니다. 예를 들어, Student 클래스가 있을 때 Student 객체끼리 정렬할 방식을 결정할 수 있습니다.
Comparator
정렬 순서를 외부에서 정의할 수 있도록 하는 인터페이스입니다. 기본 정렬 방식 외에 다른 기준으로 정렬하고 싶을 때 사용합니다. 별도의 클래스나 익명 클래스, 람다식으로 정의할 수 있습니다.

Comparable Interface

class Student implements Comparable<Student> {
    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    @Override
    public int compareTo(Student other) {
        // 점수를 기준으로 오름차순 정렬
        return Integer.compare(this.score, other.score);
    }
}

(Comparable 예제 코드)

1. Comparable과 compareTo

Student 클래스에 Comparable 인터페이스를 상속 받아 compareTo 메서드를 구현했습니다. 객체 other와 this를 비교하면서 정렬을 하는 방식입니다.

2. return 값은 negative, zero, positive

Integer.compare든 다른 어떤 메서드를 사용해도 return 값은 음수, 0, 양수 중 하나가 반환됩니다. 반환 값에 따른 의미는 다음과 같습니다.

음수 : 현재 객체(this)를 정렬 시 앞으로 배치
0 : 두 객체는 값이 같기 때문에 동일한 순서로 간주
양수 : 비교 객체(other)를 정렬 시 앞으로 배치

전 처음 이 의미를 보고 도대체 무슨 소린지 이해가 안 됐습니다.. 처음 보는 분들도 그럴 것이라 생각하고 예시와 함께 자세히 설명하겠습니다.

// 오름차순
class Example implements Comparable<T t>(){
	// 필드 중략.. //
	public int compareTo(A other){
		return this.age-other.age;
	}
}

// 내림차순
class Example implements Comparable<T t>(){
	// 필드 중략.. //
	public int compareTo(A other){
		return other.age-this.age;
	}
}

(예시는 수학적 직관을 위해 메서드가 아닌 - 연산자를 사용했습니다.)

오름차순 정렬
- return 값이 양수인 경우
  this.age 값이 더 큽니다. 그런데 양수인 경우엔 비교 객체(other)를 앞에 배치한다고 했습니다. 그럼 결과적으로 큰 값인 this.age가 other.age의 뒤에 정렬되므로 해당 정렬은 오름차순입니다.
- return 값이 음수인 경우
  this.age 값이 더 작습니다. 그런데 음수인 경우엔 현재 객체(this)를 앞에 배치한다고 했습니다. 그럼 결과적으로 작은 값인 this.age가 other.age의 앞으로 오기 때문에 마찬가지로 오름차순 정렬입니다.
내림차순 정렬
- return 값이 양수인 경우
  other.age 값이 더 큽니다. 그런데 양수인 경우엔 비교 객체(other)를 앞에 배치한다고 했습니다. 그럼 결과적으로 큰 값인 other.age가 this.age의 앞에 정렬되므로 해당 정렬은 내림차순입니다.
- return 값이 음수인 경우
  other.age 값이 더 작습니다. 그런데 음수인 경우엔 현재 객체(this)를 앞에 배치한다고 했습니다. 그럼 결과적으로 큰 값인 this.age가 other.age의 앞에 정렬되므로 해당 정렬은 내림차순입니다.

Integer.compare 같은 메서드도 똑같이 비교 결과에 따라 -1, 0, 1의 값을 반환합니다. 그리고 반환된 값은 똑같은 로직이 적용됩니다.

음수 : 첫번째 객체를 정렬 시 앞으로 배치
0 : 두 객체는 값이 같기 때문에 동일한 순서로 간주
양수 : 두번째 객체를 정렬 시 앞으로 배치

3. 정렬되는 시점

Collections.sort(students);

자연 정렬이지만 List에 객체를 추가할 때마다 정렬이 되는 건 아니고 Collections.sort 메서드로 직접 정렬해야합니다. 정렬 후 새로 객체를 추가하면 새로 추가된 객체는 정렬이 되지 않은 상태입니다.

4. this - other가 아닌 Integer.compare 메서드를 사용하는 이유

Integer.compare는 자바에 내장된 정적 메서드입니다. this.score - other.score가 수학적으로 직관적일 수 있지만 이 방식은 오버플로우(overflow) 문제를 야기할 수 있습니다. 예를 들어 this.score가 2147483647이고 other.score가 -5인 경우 음수의 부호를 반환하게 됩니다.

하지만 Integer.compare 메서드는 수학적 연산이 아닌 비트연산자를 사용하기 때문에 오버플로우가 발생하지 않습니다. 그냥 값의 대소를 비교한 뒤 결과에 따라 -1, 0, 1을 반환합니다.

아래는 자바 표준 라이브러리에 나와있는 설명입니다.

public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

삼항 연산자를 이중으로 사용해서 x가 y보다 작다면 -1을 출력, 그게 아니라 x와 y가 같다면 0을 출력하고 모두 아닌 경우엔 1을 출력하고 있습니다.

이해를 돕기 위해 if ~ else 문으로 나타내면 아래와 같습니다.

if(x < y) {
    return 1-;
} else {
    if(x == y) {
        return 0;
    } else {
        return 1;
    }
}

compare 메서드도 파고들면 무궁무진하기 때문에 다음에 제대로 정리해보도록 하겠습니다.

▶ [Java] 정적 메서드 compare에선 overflow가 발생하지 않는 이유

Comparator Interface

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>();

        // 나이를 기준으로 정렬하는 Comparator
        Comparator<Person> ageComparator = new Comparator<Person>() {
            @Override
            public int compare(Person p1, Person p2) {
                return Integer.compare(p1.age, p2.age);  // 나이 오름차순
            }
        };

        // 이름을 기준으로 정렬하는 Comparator
        Comparator<Person> nameComparator = new Comparator<Person>() {
            @Override
            public int compare(Person p1, Person p2) {
                return p1.name.compareTo(p2.name);  // 이름 오름차순 (알파벳 순)
            }
        };
    }
}

(익명 클래스를 사용한 예제 코드)

1. Comparator와 compare

익명 클래스로 Comparator 인터페이스를 구현했습니다. Comparator 인터페이스도 구현해야하는 메서드는 compare 하나입니다.

2. return 값은 Comparable과 마찬가지

return 값은 Comparable 인터페이스와 동일합니다.

3. 익명 내부 클래스 vs 기명 클래스 vs 람다식 정의

위의 예제에선 익명 내부 클래스로 작성했지만 기명 클래스나 람다식으로도 정의 가능합니다. 하지만 전 알고리즘 공부할 때는 주로 익명 내부 클래스 방식을 사용합니다.

각 정의 방식의 특징은 다음과 같습니다.

	익명 내부 클래스	기명 클래스	람다식
구현 방식	메서드 내부에서 바로 클래스 정의	별도의 클래스 정의	람다식으로 간결하게 표현
사용 시기	한번만 사용할 때	재사용이 필요할 때	코드 가독성이 중요할 때
코드 길이	긴 편	매우 김	짧고 간결
가독성	덜 직관적	명확한 구조	가장 간결하고 가독성 좋음
복잡한 로직	중간 정도의 복잡 로직에 적합	복잡한 로직에 적합	간단한 로직에 적합
도입 시기	자바 1.1	자바 1.1	자바 8

다음은 기명 클래스와 람다식으로 정의한 Comparator의 예시입니다.

// 기명 클래스: 나이 기준으로 정렬하기 위한 Comparator
class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.age, p2.age);
    }
}

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>();

        // 1. 기명 클래스(AgeComparator)를 사용하여 나이 기준으로 정렬
        Collections.sort(people, new AgeComparator());

        // 2. 람다식을 사용하여 이름 기준으로 정렬
        Collections.sort(people, (p1, p2) -> p1.name.compareTo(p2.name));
    }
}

람다식을 사용하면 익명 내부 클래스를 사용하는 방식에서 훨씬 간결한 코드로 나타낼 수 있습니다.

4. return에 들어가야하는 메서드가 따로 있는걸까?

return 문을 작성할 때 overflow 방지를 위해 단순한 수학적 연산은 안 된다는 것은 이해했습니다. 그런데 유틸리티 메서드인 compare와 compareTo 메서드의 사용 시기가 헷갈렸습니다.

그리고 저는 다음과 같이 결론 내렸습니다.

복잡한 사용자 정의 정렬을 하고 싶을 땐 compare 메서드.
기본 타입인 클래스가 구현한 자연 정렬(Comparable Interface)을 쓰고 싶을 땐 그냥 compareTo 메서드.

기본 타입인 String, Integer, Double 등의 클래스들은 이미 Comparable 인터페이스를 구현하고 있습니다. 따라서 위의 예시 코드처럼 그냥 오름차순으로 이름을 정렬하는 경우엔 compareTo 메서드를 사용했습니다. 물론 나이도 그냥 compareTo로 정렬할 수 있지만 compareTo 메서드는 래퍼 클래스인 Integer로 변환해야하기 때문에 Integer.compare 메서드를 썼습니다.

5. 문자열의 특정 인덱스 기준으로 정렬

String 클래스엔 compare 메서드가 내장되어있지 않습니다. 따라서 문자열 정렬은 compareTo 메서드를 사용해야합니다. 하지만 특정 인덱스의 문자를 기준으로 정렬을 하고 싶다면 방법이 있습니다. chatAt 메서드를 이용해 문자를 가져와서 Character.compare 메서드를 사용하는 방법입니다.

아래는 두번째 인덱스를 기준으로 문자열을 정렬하는 예제 코드입니다.

Comparator<Person> secondCharComparator = new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        char char1 = p1.name.charAt(1);
        char char2 = p2.name.charAt(1);
        return Character.compare(char1, char2);
    }
};

6. Comparator의 장점! 다중 정렬

Comparable 인터페이스와는 다르게 Comparator 인터페이스는 다중 정렬이 가능합니다. 즉, 나이순으로 정렬하고 나이가 같은 사람들끼리는 키순으로 정렬하는 등의 방식이 가능합니다.

Comparator<String> comparator = new Comparator<String>() {
    @Override
    public int compare(String a, String b) {
        int lengthComp = Integer.compare(a.length(), b.length());

        if(lengthComp != 0) {
            return lengthComp;
        }

        int charComp = a.compareTo(b);
        return charComp;
    }

};

(다중 정렬을 위한 예시 코드)

1. 위의 익명 내부 클래스로 정의된 Comparator 인터페이스는 우선 문자열의 길이를 비교합니다.

2. 만약 문자열의 길이가 다르다면 길이가 짧은 순으로 정렬을 합니다.

3. 만약 문자열의 길이가 같다면 문자열을 사전순으로 정렬합니다.

Comparable vs Comparator 한 눈에 비교

	Comparable	Comparator
목적	자연 정렬 순서를 정의	자연 정렬 순서를 벗어난 사용자 정의 정렬
메서드	compareTo(T o)	compare(T o1, T o2)
메서드 시그니쳐	int compareTo(T o)	int compare(T o1, T o2)
다중 정렬	X	O
구현 위치	객체 자체	객체 외부

마치며

처음 Comparable과 Comparator를 공부할 때 정말 혼란스러웠습니다. 처음엔 둘의 차이가 구분이 안 됐고, 쓰임을 구분하고 나니 인터페이스의 메서드인 compare와 유틸리티 메서드인 compare가 구분이 안 됐습니다. 또, 어째서 String은 String.compare 메서드가 없는건지..

백준 문제 풀면서 공부의 필요성을 느꼈는데 공부하다보니 잘못 알고 있었던 개념이나 몰랐던 부분이 너무 많다는 것을 깨닫았습니다. 그리고 이번 글을 작성하면서 더욱 확실하게 개념을 잡을 수 있었습니다. 개념이 헷갈렸던 분들은 제 글을 정말 진득하게 읽어보면 깨닫는 순간이 올거라고 믿습니다!!

Comparable과 Comparator 인터페이스가 어려웠던 분들에게 이 글이 등대가 되었으면 좋겠습니다.

궁금한 점이나 피드백은 언제나 환영합니다!

'Java' 카테고리의 다른 글

[Java] Pattern과 Matcher 클래스로 정규 표현식 제대로 사용하기 (1)	2025.01.05
[Java] Collections Framework간 변환 총정리 - List, Set, Map, Queue (1)	2024.12.03
[Java] BufferedReader 사용법과 자료구조 총정리 (1)	2024.10.18
[Java] compare 메서드에서 overflow가 발생하지 않는 이유 (0)	2024.10.14
[Java] toString과 String.valueOf 메서드 차이 (3)	2024.10.14

현재글[Java] Comparable과 Comparator로 정렬 이해하기

jundyu 님의 블로그

주로 프로젝트를 하며 새로 배운 내용을 정리하는 블로그입니다. 가볍게 여길 만한 주제들을 깊게 다루고 싶습니다.

Today :
Yesterday :

jundyu 님의 블로그