[내가 보려고 쓰는 글] JAVA 정렬 그리고 Comparable & Comparator 정리

📌 Arrays.sort & Collections.sort 

둘다 자바에서 배열을 정렬 할 때 사용된다.

1. Arrays.sort

이 메서드는 배열의 타입에 따라 다른 정렬 알고리즘을 사용한다.

즉, 프리미티브 타입과 객체 타입에 대해 다르게 동작한다.

 

1️⃣ 프리미티브 타입의 정렬 (int[], double[] 등)

프리미티브 타입의 배열을 정렬할 때 Dual-Pivot Quicksort 알고리즘을 사용한다.

두 개의 피벗을 사용해서 배열을 세 부분으로 나누고 정렬한다.

알고리즘 정보까지는 이 글이 너무 길어질 우려가 있어서 나중에 정리 글을 올리기로 한다.

이 알고리즘은 평균적으로 O(n log n)의 시간복잡도를 가지며, 최악의 경우 O(n^2)까지 갈 수 있지만, 최악의 경우가 발생할 가능성은 매우 낮다.

 

2️⃣ 객체 타입의 정렬 (Integer[], String[] 등)

객체 타입의 배열을 정렬할 때는 TimSort 알고리즘을 사용한다.

이 알고리즘은 MergeSort와 InsertionSort를 결합한 하이브리드 정렬 알고리즘이라고 한다.

이 알고리즘은 최악의 경우에도 O(n log n)의 시간복잡도를 가지며, 안정적인 정렬을 보장한다.

 

💡 Arrays.sort(Object[]) 사용시 주의할 점

👉🏻 Arrays.sort(Object[]) 사용 시에는 배열의 모든 요소가 Comparable 인터페이스를 구현해야한다.

sort 메서드가 배열의 요소들을 정렬하기 위해 비교 작업을 수행하기 때문이다.

정렬 과정에서 요소 하나하나 서로 비교를 하기 때문에 당연히 요소들은 비교가 가능해야한다.

내부 동작 시 요소 비교를 위해 Comparable 인터페이스의 compareTo()를 호출하고 있다.

따라서 반드시 객체 타입을 비교할 때는 각 요소가 Comparable을 구현하고 있는지 체크해야한다.

컴파일 단계에서는 문법적 오류가 없기 때문에 알 수 없을 뿐더러 이건 정말 위험하다.

String과 Wrapper 클래스들은 Comparable을 구현하고 있으니 괜찮지만, 그 외의 객체들은 사용 시 주의해야한다.

 

2. Collections.sort

자바에서 리스트를 정렬할 때 사용된다.

내부적으로 List의 요소들을 정렬하기 위해 Arrays.sort 메서드를 사용한다. → TimSort 알고리즘 기반

 

1️⃣ 기본 동작 원리

1. 리스트를 배열로 변환한다
2. 배열을 Arrays.sort를 사용하여 정렬한다
3. 정렬된 배열을 다시 리스트로 변환한다.

이렇게 기본 동작에서 알 수 있듯이 Arrays.sort와 마찬가지로 비교할 원소들이 Comparable을 구현한 상태여야한다.

 

💡Collections.sort 특이점

👉🏻 Collections.sort는 컴파일 단계에서 Comparable 인터페이스를 구현하지 않은 객체의 오류를 잡을 수 있다.

Arrays.sort는 컴파일 단계에서 잡아낼 수 없었지만, Collections.sort는 잡아낼 수 있다.

public static <T extends Comparable<? super T>> void sort(List<T> list)

위의 코드는 Collections.sort의 시그니처이다. 이 메서드는 제네릭 메서드로 정의되어있다.

<T extends Comparable<? super T>> 

타입 매개변수인 T가 반드시 Comparable을 구현해야 한다는 것을 나타낸다.

Comparable<? super T> : T타입이 반드시 Comparable 인터페이스를 구현해야하고, 이 인터페이스는 T 타입 또는 T의 상위 타입을 비교할 수 있어야한다는 것을 의미한다.

제네릭스는 컴파일 시 타입 체크를 수행하기 때문에 컴파일 시에 오류를 잡을 수 있게되는 것이다.

 

✅ 결론 : 같은 상황이라면 Collections.sort를 애용하자.

 

 

📌 Comparable & Comparator

 

둘다 인터페이스이며, 이름에서 알 수 있듯이 비교할 때 사용된다.

 

 

 

두 인터페이스의 차이점

Comparable : 자기 자신과 매개변수 객체를 비교한다.
Comparator : 두 매개변수 객체를 비교한다.

 

 

1. Comparable

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

실제 Comparable 인터페이스 코드이다. 내부에 compareTo 메서드만을 포함하고 있다.

따라서, Comparable의 구현체는 반드시 이 메서드를 구현해야한다.

매개변수가 하나인 것으로 유추할 수 있듯이 자기 자신과 매개변수 객체를 비교하는 인터페이스라는 것을 알 수 있다.

또한 매개변수가 객체인 것을 주의하도록 한다.

compareTo() 메서드를 오버라이딩해서 개발자가 직접 임의의 기준으로 정렬될 수 있도록 만들 수 있다.

Integer, Double, String 모두 이 Comparable을 구현하고 있어서 정렬이 가능하다.

그러나 사용자 정의 객체(내가 만든 객체)는 Comparable을 따로 구현해줘야 정렬이 가능하다.

public final class Integer extends Number
        implements Comparable<Integer>, Constable, ConstantDesc {
        
	public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }

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

Integer의 실제 코드를 보면 자기 자신과 객체로 넘어온 다른 Integer를 비교하는 것을 알 수 있다.

 

compareTo() 사용법

자기 자신과 매개 변수 객체의 차이를 비교하며 크면 양수, 같으면 0, 작으면 음수를 반환한다.

비교 결과	반환 값
자기 자신 > 매개 변수 (우선순위가 높은 경우)	양수
자기 자신 = 매개 변수	0
자기 자신 < 매개 변수 (우선순위가 낮은 경우)	음수

 

메서드의 반환값을 기준으로 하는 정렬은 기본적으로 오름차순이다. 비교 결과에 따라 객체의 순서가 결정된다.

1. 음수(-1): 현재 객체(this)가 비교 객체보다 작음. (오름차순에서 현재 객체가 앞에 위치)
2. 0: 현재 객체(this)와 비교 객체가 같음.
3. 양수(1): 현재 객체(this)가 비교 객체보다 큼. (오름차순에서 현재 객체가 뒤에 위치)

 

Integer를 예로 보자면

public int compareTo(Integer anotherInteger) {
    return compare(this.value, anotherInteger.value);
}

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

매개 변수로 넘어오는 객체인 y가 자기 자신보다 클 때는 -1을 반환 → 위치 이동이 발생, x가 앞으로 감.

y와 같을 때는 0을 반환 → 위치이동 X

y보다 x가 클 때는 1을 반환 → 위치이동X

public class Main {
    public static void main(String[] args) {
        Integer x = 3;
        Integer y = 4;
        Integer[] testInt = new Integer[2];
        
        testInt[0] = y; // 4
        testInt[1] = x; // 3

        System.out.println( x.compareTo(y) );  // -1
        System.out.println( x.compareTo(3) );  //  0
        System.out.println( x.compareTo(2) );  //  1
        Arrays.sort(testInt);
        Arrays.stream(testInt).forEach(System.out::print); //34
    }
}

⇒ 결과적으로 이렇게 오름차순이 이뤄진다.

이 메서드의 정렬은 반환 값을 기준으로 하는 것이므로 이 반환 값의 비교 조건을 바꿔서 내림차순으로 변경할 수도 있다.

( 자기 자신, 매개 변수 ) → ( 매개 변수, 자기 자신 ) 이렇게 순서를 바꾸면 내림차순이 될 것이다.

 

💡Comparable 응용법 (Student 예시)

class Student {
  private String name;
  private int score;

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

Student라는 내가 만든 객체가 있다고 가정한다.

ArrayList<Student> students = new ArrayList<>();
students.add(new Student("홍길동"), 60);
students.add(new Student("이하온"), 80);
students.add(new Student("김철수"), 40);

students.stream()
		.sorted()
		.collect(Collectors.toList())
		.forEach(System.out::println);

배열에 담아서 Collections.sort()를 통해 정렬을 시도하면 에러가 발생한다. 

👉🏻 사용자 정의 클래스 객체인 Student 객체의 정렬 기준이 없기 때문이다.

public 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 ohter) {
        return this.score - this.other;
        // return this.other - this.score;
    }
}

Comparable 인터페이스를 구현하고, compareTo메서드를 오버라이딩을 해준다.

this.score - this.other를 해주면 기존 반환값의 조건 대로 결과가 나오고, 오름차순이 될 것이다.

this.other - this.score를 해주면 기존 반환값의 조건을 반대로 뒤집었기 때문에 내림차순이 될것이다.

굳이 if로 분기처리를 하지 않고, 연산을 통해 같은 결과를 반환할 수 있게도 가능한 것이다.

 

2. Comparator

public interface Comparator<T> {
    int compare(T o1, T o2);
}

실제 Comparator 인터페이스 코드이다. 내부에 여러 메서드 중에 compare메서드를 포함하고 있다.

compare 메서드를 통해 정렬 기준을 정의할 수 있으므로 반드시 구현체에 해당 메서드를 오버라이딩해야한다.

파라미터에서 알 수 있듯이, 두 객체를 비교하는 데 사용된다.

주로 클래스가 Comparable을 구현하지 못하는 상황이거나 기본 정렬 순서 외에 다른 순서로 정렬하고자 할 때 (여러 정렬 기준이 필요할 때) 사용된다.

🙅🏻‍♀️ Comparable을 구현하지 못하는 상황

1. 외부 클래스 수정 불가의 상황

외부 라이브러리나 API의 클래스는 직접 수정할 수가 없다. 이런 클래스에는 Comparable을 구현할 수 없다.

// Comparable을 구현할 수 없으므로 Comparator를 사용
Collections.sort(list, new Comparator<ExternalClass>() {
    @Override
    public int compare(ExternalClass o1, ExternalClass o2) {
        return Integer.compare(o1.value, o2.value);
    }
});

이런 식으로 사용할 수 있겠다.

2. 자연 순서를 정의하기 어려운 경우

복잡한 데이터 구조나 특정한 비교 기준이 존재하지 않는 경우 자연 순서를 정의하기 어렵다.

3. 상속 구조로 인한 제약

클래스가 이미 다른 클래스를 상속받고 있거나, 다중 상속이 불가능한 자바에서는 추가적으로 Comparable을 구현하는 것이 불가능할 수 있다.

4. 다른 방식의 비교가 필요한 경우

비교가 특정 상황에 따라 달라지는 경우, 즉 상황에 따라 다른 기준으로 객체를 비교해야 하는 경우도 있다. 이럴 때는 Comparable보다 Comparator를 사용하는 것이 더 유연하고 적절하다.

 

compare() 사용법

비교 기준	반환 값
o1 > o2 (우선순위가 높은 경우 포함)	양수
o1 = o2	0
o1 < o2 (우선순위가 낮은 경우 포함)	음수

1. 음수: o1이 o2보다 앞에 와야 함 (오름차순에서 o1이 더 작음)
2. 0: o1과 o2가 같음
3. 양수: o1이 o2보다 뒤에 와야 함 (오름차순에서 o1이 더 큼)

반환 값에 따른 정렬은 오름차순이며, 큰 메커니즘은 compareTo()와 같다.

단지 자기 자신과 비교가 아니라 두 객체를 비교한다는 점이 다르다.

 

💡Comparator 응용법 (Person 예시)

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

내가 만든 Person 객체가 있다고 가정한다.

Person 객체를 나이는 내림차순으로 정렬하고, 나이가 같을 경우에는 이름을 오름차순(사전순)으로 정렬하고 싶다고 가정한다.

class PersonComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        // 먼저 나이를 기준으로 내림차순 비교
        int ageComparison = Integer.compare(p2.age, p1.age);
        if (ageComparison != 0) {
            return ageComparison;
        }
        // 나이가 같다면 이름을 기준으로 오름차순 비교
        return p1.name.compareTo(p2.name);
    }
}

class PersonComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        // 나이를 내림차순으로 비교
        if (p1.age != p2.age) {
            return p2.age - p1.age; // 나이가 큰 순서대로
        }
        // 나이가 같다면 이름을 오름차순으로 비교
        return p1.name.compareTo(p2.name); // 이름이 사전순으로
    }
}

이런 식으로 compare안에 알맞은 분기처리 후에 반환 값을 반환해주면 된다.

1. 위에서 다룬 내용처럼 compare에 비교값 순서를 바꿔서 내림차순으로 만들어준다. or 빼기 연산으로 구현한다.
2. 값이 같지 않다면 그대로 값을 반환하고, 나이가 같다면 이름을 기준으로 오름차순을 비교할 수 있도록 compareTo를 사용한다.

public class Main {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>();
        people.add(new Person("Alice", 30));
        people.add(new Person("Bob", 25));
        people.add(new Person("Charlie", 35));
        people.add(new Person("David", 30));
        people.add(new Person("Eve", 25));

        // 나이 기준 내림차순, 이름 기준 오름차순 정렬
        Collections.sort(people, new PersonComparator());
        System.out.println(people);
        // [Charlie (35), Alice (30), David (30), Bob (25), Eve (25)]
    }
}

 

이런 식으로 활용할 수 있게 된다.

 

📌 참고글

https://haon.blog/java/comparable-comparator/

샤라웃 챗gpt