[문법] Comparator, Comparable 정렬 원리

서론

자바의 객체 정렬 기준에 대해 알아봅니다.

 

본론

- Comparator와 Comparable

객체 정렬에 필요한 메서드를 정의한 인터페이스로 정렬 기준을 제공하는 것이 목적입니다.

 

class Student {
    String name;
    int ban;
    int totalScore;
}

즉, 객체를 비교할 수 있도록 만듭니다. 자바에서 제공하는 primitive 타입은 부등호 비교가 가능하지만 Student 클래스는 이름, 학급, 점수 중 어떠한 것을 정렬 기준으로 비교해야 하는지 알 수 없고 정해줘야 합니다. 이때, 정렬 기준 인터페이스를 사용하여 메서드를 재정의 함으로써 정렬 기준을 명시합니다.

 

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

 

Comparable은 compareTo 메서드에 비교 기준을 정의함으로써 이를 구현한 클래스의 객체에 비교 기준을 지정합니다. compareTo 메서드의 인자로 비교 대상을 받아 자기 자신과 비교합니다.

 

자신이 더 크면 : 양수
같으면 : 0
자신이 더 작으면 : 음수

비교 결과는 다음과 같습니다. 이를 정렬에 활용하게 되면 선행 원소가 자기 자신이 되고, 후행 원소가 매개 변수 o가 됩니다.

 

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

Comparator는 compare 메서드를 가지고 o1, o2를 비교하여 양수, 0, 음수를 반환합니다. 자기 자신의 상태가 어떠하든 상관없이 인자 2개를 비교합니다. 이를 정렬에 적용하면 선행 원소가 o1, 후행 원소가 o2가 됩니다. 

 

public static Comparator<Student> comp2 = new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.ban - o2.ban;
    }
};

Comparator의 비교 기능은 이를 호출한 레퍼런스와 관계 없이 인자로 들어온 매개변수 2개를 비교하기 때문에 익명 객체로 활용하는 경우가 더 많습니다. 단지, 정렬 기준 용으로 이름 없는 클래스를 만든 것이고

 

(Student o1, Student o2) -> (o1.ban - o2.ban);

따라서 람다 익명 객체로 단순화 할 수 있습니다.

 

-> 정렬

정렬이란, 두 대상을 비교해서 자리 바꿈을 반복하는 것인데 Comparator와 Comparable로 객체의 정렬 기준을 지정합니다. 자바의 기본 정렬 기준은 오름차순이며 compare 메서드를 정의하여 사람을 나이, 몸무게, 성적으로 정렬할 수 있습니다.

 

public final class Integer extends Number implements Comparable<Integer> {


    public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }
    
    public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }

이 두 정렬 기준이 되는 인터페이스는 정렬을 하고 싶은 객체를 구현하면 됩니다. Integer 클래스에 compareTo를 구현하면 현재 정수와 인자로 들어온 정수를 비교하여 0, 1, -1을 반환합니다. 이때 후행 요소가 인자로 들어옵니다.

 

오름차순에서는 [7, 5]가 있으면 자리 바꿈을 해야하고 내림차순이면 [5, 7]일 때 자리 바꿈을 해야 하며 정렬 방식(오름차순, 내림차순) 마다 자리 바꾸는 기준이 다를 것입니다.

 

따라서, 오름차순 정렬은 왼쪽값이 크면 1, 오른쪽 값이 크면 -1을 반환하도록 구현되어있습니다. 이 값들로 어떻게 오름, 내림 차순을 수행하나 Sort 메서드 내부를 분석해 보겠습니다.

 

- Arrays sort 메서드 내부

sort 메서드는 정렬 대상과 정렬 기준을 인자로 받으며, 정렬 대상 클래스 내부에 compare 메서드가 재정의 되어 있는 경우 정렬 기준을 안 넣어줘도 됩니다. 정렬 기준이 없는 경우 sort(배열)가 호출되고

 

merge sort로 자연 순서에 따라 지정된 개체 배열을 오름차순 정렬합니다.

 

Integer의 기본 정렬의 경우 왼쪽이 더 크면 1로 compare 메서드가 재정의 되어 있습니다. Integer 형이면 compareTo, int형이면 compare 메서드를 사용합니다.

 

✅ 이 부분이 매우 중요합니다.

여기에 compareTo 메서드를 사용하여 정렬을 하는 방법이 나와있습니다. for문 조건에 따라 compareTo 결과가 0보다 크면 swap 합니다. 그 이유는 기본 정렬이 오름차순 정렬인데 만약 선행 요소가 7이고 후행 요소가 5이면 양수를 반환하여 둘의 순서를 바꾸기 위함입니다. 만약 내림차순을 하고 싶다면 compareTo 메서드의 양수 반환 기준을 오른쪽 값이 더 크면 반환하도록 바꿔야 할 것입니다. 이처럼 정렬 방식에 맞게 다르게 구현해야 합니다.

 

-> 예제

위 정의를 사용하면 객체의 어떠한 필드도 정렬 기준으로 사용할 수 있습니다. compareTo 메서드의 재정의를 양수, 음수, 0으로만 반환하면 문자열의 길이나 문자열의 첫 글자 등으로도 정렬 기준을 잡을 수 있습니다.

 

String[] strs = {"cat", "Dog", "lion", "tiger"};

Arrays.sort(strs);
Arrays.stream(strs).forEach(s -> System.out.print(s + ' '));
System.out.println();

Arrays.sort(strs, String.CASE_INSENSITIVE_ORDER);
Arrays.stream(strs).forEach(s -> System.out.print(s + ' '));
System.out.println();

Comparator desc = new Comparator<String>() {

    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2) * -1;
    }
};
Arrays.sort(strs, desc);
Arrays.stream(strs).forEach(s -> System.out.print(s + ' '));
System.out.println();

Arrays.sort(strs, (String str1, String str2) -> (str1.length() > str2.length() ? -1 : 1));
Arrays.stream(strs).forEach(s -> System.out.print(s + ' '));

 

1) String 기본 정렬

정렬 대상이 정렬 기준을 가지고 있는 경우는 sort의 인자로 정렬 대상만 줘도 됩니다. Integer처럼 String도 implement Comparable를 가지고 있어서 내부 compareTo 메서드를 정렬 기준으로 사용합니다.

 

String의 compareTo 메서드를 수정하면 정렬 기준을 바꿀 수 있지만 자바가 제공하는 클래스라서 수정은 못하고 다음 예시처럼 원하는 정렬 기준을 인자로 넣어주면 됩니다.

2) Arrays.sort(strArr, CASE_INSENSITIVE_ORDER)

정렬 기준을 넣어주면 해당 정렬 기준을 사용하여 동일하게 병합 정렬을 수행합니다. 정렬 기준을 넣지 않으면 클래스 내부에 재정의한 정렬 기준을 사용하고 그렇지 않으면 추가로 정렬 기준을 넣어줘야 합니다.

 

CASE_INSENSITIVE_ORDER는 대소문자를 구분하지 않는 정렬 기준입니다.

3) Arrays.sort(strArr, 내림차순 정렬 기준)

내림차순으로 정렬하고 싶으면 Comparator의 compare을 내림차순 정렬로 구현하면 됩니다. 기본 정렬 기준의 결과에 -1을 곱하면 내림차순 정렬이 가능합니다.

 

 

Arrays.sort(strs, (String str1, String str2) -> (str1.length() > str2.length() ? -1 : 1));

익명 객체 사용을 통해 람다형으로 훨씬 간단하게 정렬을 할 수 있다는 것을 짐작할 수 있습니다. 람다도 익명 객체의 함수형 표현법이므로 적용 가능합니다.

 

- 모든 테스트 케이스 확인해 보기 ✅

스트림을 쓰는 경우와 안 쓰는 경우, comparable을 쓰는 경우와 comparator를 쓰는 경우를 배열, 리스트, 사용자 지정 객체를 정렬하는 경우에 모두 적용하여 비교해 보겠습니다.

 

-> Student 객체

class Student implements Comparable<Student>{
    String name;
    int ban;
    int totalScore;

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

사용자 지정 객체는 이름, 반, 총점을 가지고 있고 이를 정렬 기준으로 사용할 것입니다.

 

-> 전체 시나리오

Student[] students = {
        new Student("a", 7, 200),
        new Student("a", 7, 500),
        new Student("b", 8, 600)
};

for (Student student : students) {
    System.out.println(student);
}

Arrays.sort(students);

System.out.println();
for (Student student : students) {
    System.out.println(student);
}

Arrays의 sort 메서드는 정렬 대상만 입력하면 기본 오름차순 정렬을 합니다. 그렇다면 Comparator나 Comparable이 양수나 음수를 반환하는 것에 따라 어떤 정렬이 적용되는 지 알 수 있을 것입니다.

 

또한 Comparator의 경우 compare 메서드로 왼쪽과 오른쪽을 받는 데 compareTo는 하나만 받기에 실제로 선행 요소가 자기 자신이고 후행 요소가 인자인지 로그로 확인하고자 합니다.

 

-> 스트림을 사용하지 않은 경우

1. comparable 쓸 때

@Override
public int compareTo(Student o) {
    return this.totalScore > o.totalScore ? 1 : -1;
}

 

-> 결과

this가 큰 경우 양수가 return 되면 오름차순으로 정렬됩니다.

 

@Override
public int compareTo(Student o) {
    return this.totalScore < o.totalScore ? 1 : -1;
}

 

-> 결과

this가 작은 경우 양수가 return 되면 내림차순으로 정렬됩니다.

 

@Override
public int compareTo(Student s) {
    return this.totalScore - s.totalScore;
}

 

this가 왼쪽에 있으면 오름차순으로 정렬됩니다.

 

@Override
public int compareTo(Student s) {
    return s.totalScore - this.totalScore;
}

 

-> 결과

this가 오른쪽에 있으면 내림차순으로 정렬됩니다.

 

-> 정리

스트림을 사용하지 않고 comparable의 compareTo 메서드를 사용했을 때 1) this가 큰 경우 양수가 반환되면 오름차순이 되고 2) 매개변수가 큰 경우 양수가 반환되면 내림차순이 됩니다.

오름차순의 경우 7, 5이면 자리를 바꿔야 하고 내림차순의 경우 5, 7이면 자리를 바꿔야 하는데 오름차순을 하고 싶으면 1) this가 크거나 3) 왼쪽에 있는 경우 양수를 반환해야 하고 내림차순이 하고 싶으면 2) this가 작거나 4) 오른쪽에 있는 경우 음수를 반환하면 됩니다.

즉 sort 메서드에 구현되어 있는 것처럼, 양수가 반환되면 sort 메서드에 자리를 바꾸라고 알려주는 것이고 오름차순 정렬의 경우 this가 크거나 왼쪽에 있는 경우 양수를 반환하여 자리를 바꾸게 해야 하는 것을 확인할 수 있었고 this가 선행, 인자가 후행임을 알 수 있습니다.

 

-> 람다식으로 조건 적용

Arrays.sort(students, (Student::compareTo));
System.out.println(Arrays.toString(students));

람다식을 적용하기 위해서는 compareTo 메서드를 만들고 메서드 참조를 사용하면 됩니다. compareTo 메서드에 반, 총점을 골라서 구현하면 원하는 기준으로 정렬할 수 있습니다.

 

1. comparator 쓸 때

사용자 정의 객체의 경우 Comparator를 객체에 직접 구현하면 이러한 에러가 발생합니다. 따라서 Comparator를 스트림으로 쓰던가 Comparator 익명 객체를 따로 만들어줘야 합니다.

 

1) 왼쪽이 큰 경우

class Sort implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.totalScore > o2.totalScore ? 1 : -1;
    }
}

Arrays.sort(students, new Sort());

Comparator 익명 객체를 따로 만들고 sort 메서드의 정렬 기준으로 넣어주면 됩니다.

 

-> 결과

왼쪽이 큰 경우 양수가 return 되면 오름차순으로 정렬됩니다.

 

2) 오른쪽이 큰 경우

class Sort implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.totalScore < o2.totalScore ? 1 : -1;
    }
}

 

-> 결과

오른쪽이 큰 경우 양수가 return 되면 내림차순으로 정렬됩니다.

 

-> 람다식 적용

Arrays.sort(students, (Student s1, Student s2) -> s1.totalScore < s2.totalScore ? 1 : -1);

compare 메서드에 구현한 그대로 람다식을 작성하면 됩니다.

 

-> 정리

역시 오름차순을 하고 싶으면 왼쪽이 큰 경우 양수를 반환하면 되고 내림차순을 하고 싶으면 오른쪽이 큰 경우 양수를 반환하여 자리를 바꾸라고 알려주면 됩니다. 앞에서 정리한 내용대로 선행, 후행 요소를 사용하여 비교하는 것임을 알 수 있습니다.

 

compareTo는 선행요소가 this인지 확인 ✅

@Override
public int compareTo(Student s) {
    System.out.println("this " + this.toString());
    System.out.println("args " + s.toString());

    return this.totalScore < s.totalScore ? 1 : -1;
}

내림차순을 희망하는 상황에서 this와 매개변수를 로그로 남겨보겠습니다. 내림차순이 되려면 오른쪽이 클 때 양수를 반환해야 합니다.

 

내림 차순은 원하는 대로 되었지만,

 

this : 후행요소
인자 : 선행요소

인자와 this의 관계는 예상과 반대로 나왔습니다.

그러면 compare를 구현할 때와 compareTo를 구현할 때 sort 메서드가 다르게 동작하는 것일까요? ✅

compare과 compareTo는 오름차순, 내림차순을 위해 그저 양수, 0, 음수만 반환하는 것이고 그때 sort가 각각 어떻게 동작하는 지를 알아야 할 것 같습니다.

 

private static void mergeSort(Object[] src,
                              Object[] dest,
                              int low, int high, int off,
                              Comparator c) {
    int length = high - low;

    // Insertion sort on smallest arrays
    if (length < INSERTIONSORT_THRESHOLD) {
        for (int i=low; i<high; i++)
            for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
                swap(dest, j, j-1);
        return;
    }

정렬을 보면 compare() 메서드를 사용하며 머지 sort를 사용합니다. 단순히 왼쪽 오른쪽의 위치를 봐서 위치를 바꾸는 줄 알았는데 머지 소트를 사용하여 정렬을 하는 것이고 따라서 this와 매개변수의 위치는 정해져 있는 것이 아니고 둘 중 무엇이 크냐에 따라서 SWAP을 할지 말지를 결정하는 것이었습니다. 

 

-> 결론

compareTo에서 선행 요소가 항상 this라는 설명은 정확하지 않고, 정렬 과정에서 this와 인자의 역할은 상황에 따라 달라질 수 있으며 현재 비교 대상을 나타낸다.

 

-> 스트림으로 정렬

Stream<Student> stream = Arrays.stream(students);

// 오름차순
stream.sorted(Comparator.comparing(Student::getTotalScore))
    .forEach(System.out::println);
           
// 내림차순
stream.sorted(Comparator.comparing(Student::getTotalScore).reversed())
    .forEach(System.out::println);

스트림을 사용하면 위처럼 편하게 특정 기준으로 오름차순 정렬할 수 있고 내림차순도 할 수 있습니다.

 

Stream<Student> stream = Stream.of(students);

stream.sorted(Comparator.comparing(Student::getTotalScore).reversed()
                .thenComparing(Comparator.comparing(Student::getBan).reversed()))
        .forEach(System.out::println);

이처럼 내림차순을 적용하고 다른 기준을 또 지정할 수 있어서 Comparator나 Comparable을 구현하지 않고 빠르고 간결하게 정렬을 할 수 있습니다.

2. comparable 쓸 때

@Override
public int compareTo(Student o) {
    return this.totalScore > o.totalScore ? 1 : -1;
}

객체는 Comparator는 직접적으로 구현할 수 없어서 comparable을 위에서 공부한 규칙대로 오름차순으로 구현하고 

stream.sorted(Comparator.comparing(Student::getBan)
            .thenComparing(Comparator.naturalOrder()))
    .forEach(System.out::println);

naturalOrder()로 기본 정렬 기준을 주면 반 별로 정렬하고 반이 같은 경우 총점을 오름차순으로 정렬합니다.

stream.sorted(Comparator
            .comparing(Student::getMoney)
            .reversed())
    .sorted(Comparator
            .comparing(Student::getName)
            .reversed())
    .forEach(System.out::println);

이렇게 하면 2차 정렬이 안 됩니다.

 

=> 배열

배열을 정렬하는 경우를 알아봅니다.

-> 스트림을 사용하지 않은 정렬

1. 정수 정렬
1) 오름 차순

int[] arr = {1, 7, 3, 4, 3, 6, 1, 2, 8};

System.out.println(Arrays.toString(arr));
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));

사용자 지정 객체에서는 정렬의 기준이 필요해서 Comparator를 사용한 건데 기본 자료형이나 Integer 같은 자료형은 내부에 compare 메서드가 재정의 되어 있어서 정렬 기준이 필요 없습니다. 하지만 2차원 배열부터는 정렬의 기준을 줄 수 있습니다.

2) 역정렬

int[] arr = {1, 7, 3, 4, 3, 6, 1, 2, 8};

System.out.println(Arrays.toString(arr));

Integer[] integers = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(integers, Comparator.reverseOrder());

정수형 배열의 경우 reverseOrder를 사용할 수 없어서 Interger 배열로 바꿔야 합니다.

 

double[] arr = {1, 7, 3, 4, 3, 6, 1, 2, 8};

System.out.println(Arrays.toString(arr));

Double[] doubles = Arrays.stream(arr).boxed().toArray(Double[]::new);
Arrays.sort(doubles, Comparator.reverseOrder());

실수 또한 역정렬이 불가능하여 Double Wrapper로 변환해야 합니다.

2. 문자열 정렬
1) 오름 차순 정렬

String[] strArray = {"aa", "ac", "ab", "ad"};

System.out.println(Arrays.toString(strArray));
Arrays.sort(strArray);

2) 역정렬

String[] strArray = {"aa", "ac", "ab", "ad"};

System.out.println(Arrays.toString(strArray));
Arrays.sort(strArray, Comparator.reverseOrder());

문자열 배열은 reverseOrder()로 역정렬이 가능합니다.

 

-> 람다식 사용

String[] strArray = {"aac", "ac=7", "a", "ad33333"};

System.out.println(Arrays.toString(strArray));
Arrays.sort(strArray, (String x, String y) -> Integer.compare(x.length(), y.length()));
System.out.println(Arrays.toString(strArray));

람다식을 이용하여 문자열을 길이에 따라 정렬할 수 있습니다. Integer의 compare 메서드 또한 왼쪽이 크면 1 오른쪽이 크면 -1을 반환합니다. 따라서 이 람다식은 오름차순 정렬이며

 

Arrays.sort(strArray, (String x, String y) -> Integer.compare(x.length(), y.length()) * -1);

이는 내림차순 정렬입니다.

 

-> 스트림으로 정렬

1. 정수 정렬
1) 오름 차순 정렬

int[] arr = {1, 7, 3, 4, 3, 6, 1, 2, 8};
IntStream stream = Arrays.stream(arr);
stream.sorted()
                .forEach(System.out::println);

정수형 스트림으로 만들어야 합니다.

2) 역정렬

역정렬을 하려 했으니 따로 조건을 넣을 수 있는 부분이 없으므로 위에서 한 것처럼 Interger 배열로 바꾸고 reverseOrder()를 써야 합니다.

 

2. 문자열 정렬
1) 오름차순 정렬

String[] strArray = {"aa", "ac", "ab", "ad"};
Stream<String> strStream = Stream.of(strArray);
strStream.sorted()
                .forEach(System.out::println);

2) 역정렬

String[] strArray = {"b", "d", "a", "e"};
Stream<String> strStream = Stream.of(strArray);
strStream.sorted(Comparator.reverseOrder())
                .forEach(System.out::println);

 

=> 리스트

리스트를 정렬하는 경우를 알아봅니다.

 

-> 기본 정렬

Integer[] arr = {1, 7, 3, 4, 3, 6, 1, 2, 8};

// List로 해보기
List<Integer> list = Arrays.asList(arr);
list.sort(Comparator.naturalOrder());

// Collections이 더 직관적임
Collections.sort(list);

 

Collections 클래스의 sort 메서드는 정렬 대상과 기준을 받아서 list.sort(정렬 기준)을 하는 것으로 구현되어 있습니다.

 

-> 스트림을 사용하지 않은 정렬

Integer[] arr = {1, 7, 3, 4, 3, 6, 1, 2, 8};

// List로 해보기
List<Integer> list = Arrays.asList(arr);
list.sort(Comparator.reverseOrder());

컬랙션이므로 기본적으로 sort() 메서드를 가지고 있습니다.

 

-> 스트림을 사용하는 경우

Integer[] arr = {1, 7, 3, 4, 3, 6, 1, 2, 8};

// List로 해보기
List<Integer> list = Arrays.asList(arr);
list.stream()
        .sorted(Comparator.reverseOrder())
        .forEach(System.out::println);

컬랙션을 스트림으로 변환하는 stream()를 사용하면 됩니다.

 

결론

정렬을 stream을 사용하는 경우와 사용하지 않는 경우 정렬 대상과 정렬 기준을 어떻게 줘야 하는지 고민해 보는 시간이었습니다. 스트림을 사용하면 이전보다 훨씬 간결하게 코드를 짤 수 있습니다.