[Java] 정렬(Sorting) : Comparator과 Comparable

 

 

정렬

Java에서 배열과 컬렉션과 같은 데이터의 집합을 정렬하는 방법들에 대해서 살펴보겠다.

기본적인 정렬 방법부터, Comparator과 Comparable의 개념과, 둘의 사용 목적에 대해서 살펴보려고 한다.

추가적으로 Java에서 사용되는 정렬 알고리즘에 대해서 알아보자.

 

 

---

배열 : 기본 정렬 방법 

 

int[] array = {5, 2, 8, 1, 9};

// 배열 오름차순 정렬
Arrays.sort(array);
System.out.println(Arrays.toString(array));
// [1, 2, 5, 8, 9]

 

기본적으로 정렬 시, Arrays.sort(data) 메서드를 이용한다.

이는 따로 리턴 타입이 있지 않고, 메서드 내부에서 집합을 정렬하여 재배치하게 되기 때문에 array 변수 자체의 순서가 변하게 된다.

 

// int[] array = {5, 2, 8, 1, 9}; //Error
Integer[] array = {5, 2, 8, 1, 9};

// 배열 내림차순 정렬
Arrays.sort(array, Collections.reverseOrder());
System.out.println(Arrays.toString(array));
// [9, 8, 5, 2, 1]

 

내림차순으로 정렬할 때에는 Arrays.sort(data, Collections.reverseOrder()) 메서드처럼 인자를 추가하여 준다.

주의할 점은 int와 같은 Primitive Type의 경우 사용이 안된다. 따라서 Integer와 같이 Wrapper Class를 사용해주었다.

 

 

 

배열 : String 정렬

 

String[] array = {"Hello", "World", "Java"};

// 배열 오름차순 정렬
Arrays.sort(array);
System.out.println(Arrays.toString(array));
//[Hello, Java, World]

String[] array = {"Hello", "World", "Java"};

// 배열 내림차순 정렬
Arrays.sort(array, Collections.reverseOrder());
System.out.println(Arrays.toString(array));
//[World, Java, Hello]

 

String과 같은 다른 데이터 타입의 경우에도 정렬이 가능하다. 이는 클래스 내부에 Comparable을 구현하여 오버라이딩된 compareTo() 메서드에 의해서 정렬의 순서가 결정되고, String의 compareTo()에서는 문자열을 사전식(A-z 이런 식으로) 정렬되도록 설정되어 있다.

compareTo()에 대해서는 뒤에서 살펴보도록 하겠다.

 

 

 

 

---

Comparator

 

객체의 순서를 비교하고 정렬하는 데 사용되는 인터페이스이다. 

여기에는 compare() 메서드가 정의되어 있다. 해당 메서드는 두 개의 객체를 매개변수로 받아서 비교하는 로직에 따라서 양수, 0, 음수를 반환한다.

• 음수를 반환하면 첫 번째 매개변수가 두 번째 매개변수보다 정렬 우선순위가 높다(앞에 위치)
• 0을 반환하면 두 매개변수의 정렬 우선순위가 동일
• 양수를 반환하면 첫 번째 매개변수가 두 번째 매개변수보다 정렬 우선순위가 낮다(뒤에 위치)

 

public class SortExample {
    public static void main(String[] args) {
        Integer[] array = {5, 2, 8, 1, 9};
        Arrays.sort(array, new MyReserverComparator());
        System.out.println(Arrays.toString(array));
        // [9, 8, 5, 2, 1]
    }

}

class MyReserverComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}

 

해당 코드는 Comparator 인터페이스를 구현하여 배열을 내림차순으로 정렬하는 내용을 작성한 것이다.

만약 o1에 2, o2에 9가 들어왔다고 생각해보자. 이 때 반환값은 양수이므로 2가 9보다 정렬 우선순위가 낮다. 따라서 9가 2보다 앞에 위치한다.

마찬가지로 o1에 9, o2에 2가 들어왔다고 생각해보자. 이 때 반환값은 음수이므로 9가 2보다 정렬 우선순위가 높다 . 이 경우에도 9가 2보다 앞에 위치한다.

 

 

---

Comparator : 익명 클래스

Integer[] array = {5, 2, 8, 1, 9};

Arrays.sort(array, new Comparator<Integer>(){
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});
System.out.println(Arrays.toString(array));
// [9, 8, 5, 2, 1]

 

보통 Comparator은 일회성으로 사용되기 때문에 위의 코드처럼 익명 클래스의 형태로 주로 사용되고는 한다.

 

 

 

---

Comparator : 람다식

Integer[] array = {5, 2, 8, 1, 9};

Arrays.sort(array, (o1, o2) -> o2 - o1);
System.out.println(Arrays.toString(array));
// [9, 8, 5, 2, 1]

 

간단한 형태라면, 람다식 표현을 사용해서 코드를 압축할 수 있다.

 

 

함께 보기

 

https://sjh9708.tistory.com/189

[Java] 내부 클래스(Inner Class) (멤버, 정적, 지역, 익명 내부 클래스)

https://sjh9708.tistory.com/190

[Java] 람다식(Lambda Expression)과 함수형 프로그래밍

 

 

---

복잡한 조건의 정렬

Integer[] array = {5, 2, 8, 1, 9};

Arrays.sort(array, new Comparator<Integer>(){
    @Override
    public int compare(Integer o1, Integer o2) {
        if (o1 % 2 == 0 && o2 % 2 != 0) { // o1이 짝수이고 o2가 홀수인 경우
            return 1; // o1을 o2보다 뒤로 정렬
        } else if (o1 % 2 != 0 && o2 % 2 == 0) { // o1이 홀수이고 o2가 짝수인 경우
            return -1; // o1을 o2보다 앞으로 정렬
        } else { // 둘 다 홀수이거나 둘 다 짝수인 경우, 또는 둘 다 같은 경우
            return o1 - o2; // 기존의 오름차순 정렬을 유지
        }
    }
});

System.out.println(Arrays.toString(array));
// [1, 5, 9, 2, 8]

 

compare 함수의 원리를 파악했으니, 오름차순/내림차순 이외에도 다양한 조건에 의해서 정렬되도록 구현할 수 있을 것이다.

위의 코드는 홀수를 짝수보다 먼저 정렬되도록, 같은 홀수, 혹은 짝수끼리는 오름차순 순으로 정렬되도록 작성한 코드이다.

 

 

 

---

객체의 정렬

 

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

 

그렇다면 다음과 같은 클래스의 집합은 어떻게 정렬될까? 

우리는 우선 이 생각이 들어야 한다. 과연 컴파일러가 이 Object를 알아서 정렬할 수 있을까? 불가능할 것이다. 

객체를 정렬하기 위해서는 Comparable 또는 Comparator를 구현해야 하고, 이를 토대로 컴파일러가 정렬을 할 것이다.

 

public class SortExample {
    public static void main(String[] args) {
        Human h1 = new Human("Kim", 20);
        Human h2 = new Human("Lee", 30);
        Human h3 = new Human("Park", 10);
        Human[] array = {h1, h2, h3};
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));

    }
}

 

만약 위의 인터페이스를 구현하지 않고 시도하게 되면 아래의 오류가 발생하게 된다.

java.lang.ClassCastException : class string.Human cannot be cast to class java.lang.Comparable

우리는 Comparable이 없어서 정렬하지 못한다는 것을 Exception Message를 메시지를 통해서 유추할 수 있다.

 

 

Compatator로 시도

public class SortExample {
    public static void main(String[] args) {
        Human h1 = new Human("Kim", 20);
        Human h2 = new Human("Lee", 30);
        Human h3 = new Human("Park", 10);
        Human[] array = {h1, h2, h3};
        Arrays.sort(array, (o1, o2) -> o1.age - o2.age);
        System.out.println(Arrays.toString(array));
        //[Park / 10, Kim / 20, Lee / 30]

    }
}

 

해당 코드는 위에서 사용했던 Comparator를 사용하여 sort 메서드에 매개변수로 정렬 방법을 전달한 것이다.

이러면 이제 컴파일러는 어떤 형식으로 객체를 정렬해야 하는 지 알고 있는 상태이므로 정렬이 가능하다.

 

 

---

Comparable

 

위에서는 객체의 정렬을 Comparator를 통해서 수행하였다. 이번에는 Comparable을 객체 내부에서 구현하여 정렬 방식을 해당 클래스내부에 정의하는 방식으로 사용해 보려고 한다.

 

이제 우리는 클래스 내부에서 Comparator 인터페이스를 구현하고 compareTo() 메서드를 오버라이딩하여 객체 자체에 대한 정렬 기준을 정의하려고 한다.

이를 통해서 객체를 정렬할 때 마다 Comparator를 구현할 필요가 없이, 해당 객체가 디폴트로 정렬되는 방법을 지정할 수 있는 것이다.

 

 

class Human implements Comparable<Human>{
    public String name;
    public int age;
    public Human(String name, int age){
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Human other) {
        return this.age - other.age;
    }

    @Override
    public String toString() {
        return name + " / " + age;
    }

}

 

다음 코드는 Comparable 인터페이스를 구현하였으며, compareTo를 Override하였다.

compareTo에서 파라미터는 해당 객체와 비교할 다른 객체이며, 정렬 규칙은 Comparator과 같다.

• 음수를 반환하면 해당 객체가 대상 객체보다 정렬 우선순위가 높다(앞에 위치)
• 0을 반환하면 두 객체의 정렬 우선순위가 동일
• 양수를 반환하면 첫 번째 객체가 두 번째 객체보다 정렬 우선순위가 낮다(뒤에 위치)

 

Human h1 = new Human("Kim", 20);
Human h2 = new Human("Lee", 30);
System.out.println(h1.compareTo(h2)); // -10

 

실제로 compareTo() 메서드를 호출해 보면 결과로 -10이 나오며, 이는 h1이 h2보다 정렬 시 앞에 위치하게 된다는 것을 의미한다.

 

 

class Human implements Comparable<Human>{
    public String name;
    public int age;
    public Human(String name, int age){
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Human other) {
        return this.age - other.age;
    }

    @Override
    public String toString() {
        return name + " / " + age;
    }

}

public class SortExample {
    public static void main(String[] args) {
        Human h1 = new Human("Kim", 20);
        Human h2 = new Human("Lee", 30);
        Human h3 = new Human("Park", 10);
        
        Human[] array = {h1, h2, h3};
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        // [Park / 10, Kim / 20, Lee / 30]

    }
}

 

Compable을 구현했으면 이제, Arrays.sort() 시, Comparator을 인자로 넘겨주지 않아도 객체에서 구현된 Comparable에 의한 정렬 규칙에 따라서 정렬이 가능하게 된다.

 

 

---

자바 클래스에서 Comparable 살펴보기

 

  public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    
  	public int compareTo(String anotherString) {
        byte v1[] = value;
        byte v2[] = anotherString.value;
        if (coder() == anotherString.coder()) {
            return isLatin1() ? StringLatin1.compareTo(v1, v2)
                              : StringUTF16.compareTo(v1, v2);
        }
        return isLatin1() ? StringLatin1.compareToUTF16(v1, v2)
                          : StringUTF16.compareToLatin1(v1, v2);
     }
     
   }

 

자바에서 제공되는 String 클래스에 대해서 극히 일부의 내용이다. 앞에서 가장 기본적인 정렬에 대해서 봤을 때 String이 당연하게 정렬되었다. 이는 String 클래스 내부에 Comparable이 구현되어져 있었기 때문에 가능했던 일이다.

 

 

 

 

---

Comparator vs Comparable

 

Comparable은 클래스 자체에 정렬 기준을 정의하므로 기본적으로 사용하기 편리하다.

Comparator는 외부에서 여러 가지 정렬 기준을 제공할 수 있으므로 상황에 따라서 정렬 기준을 정의할 수 있는 유연성이 좋다.

 

따라서 클래스에 기본적인 Comparable을 구현하여 디폴트 정렬 방식을 정의해 두고

외부에서 객체의 정렬 기준을 변경해야 할 일이 생길 때에 Comparator를 사용하는 것이 적절할 것이다.

 

 

 

---

Collection : 정렬

 

class Human implements Comparable<Human>{
    public String name;
    public int age;
    public Human(String name, int age){
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Human other) {
        return this.age - other.age;
    }

    @Override
    public String toString() {
        return name + " / " + age;
    }

}

public class SortExample {
    public static void main(String[] args) {
        Human h1 = new Human("Kim", 20);
        Human h2 = new Human("Lee", 30);
        Human h3 = new Human("Park", 10);

        List<Human> list = new ArrayList<>();
        list.add(h1);
        list.add(h2);
        list.add(h3);
        
        Collections.sort(list);
        System.out.println(list);
        // [Park / 10, Kim / 20, Lee / 30]

        Collections.sort(list, (o1, o2) -> o2.age - o1.age);
        System.out.println(list);
        // [Lee / 30, Kim / 20, Park / 10]

    }
}

 

Collection에서도 Array와 유사하게 정렬을 수행할 수 있다.

Collections 클래스에서 Collections.sort() 메서드를 지원하며, 이는 Arrays.sort()와 사용법이 거의 동일하다.

위의 코드는 Comparator와 Comparable을 둘 다 사용해서 컬렉션을 정렬하는 예제 코드이다.

 

 

 

 

---

Java의 정렬 알고리즘

 

sort() 메서드는 일반적으로 합병 정렬(Merge Sort) 또는 퀵 정렬(Quick Sort)을 기반으로 구현된다.

 

 

합병 정렬(Merge Sort)

• 시간 복잡도 : O(n log n)
• 공간 복잡도 : 일반적으로 O(n), 입력 배열의 크기에 따라 증가

퀵 정렬(Quick Sort)

• 시간 복잡도 : 평균 O(n log n), 최악의 경우 O(n^2)
• 공간 복잡도 : O(log n) -> 추가적인 메모리를 필요로 하지 않음
• 동일한 값에 대한 순서가 유지되지 않을 수 있다
• 퀵 정렬 중 단일 피벗보다 성능이 좋은 이중 피벗 퀵 정렬을 사용한다.

 

public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

 

위의 코드들은 자바에서 Arrays 클래스의 일부분이며, 실제로 이것보다 더 많은 케이스의 sort()가 있지만 합병 정렬과 퀵 정렬이 사용되는 것을 확인할 수 있다.

 

더 깊게 살펴보면 사용되는 알고리즘은 아래와 같다.

 

Arrays.sort(): 배열을 정렬하는 데 사용되는 방법이다. 퀵 정렬과 병합 정렬을 결합한 듀얼 피벗(Dual-Pivot) 퀵 정렬을 사용한다.

• 삽입 정렬과 퀵 정렬을 합친 형태이며, 작은 배열에 대해서는 삽입 정렬을, 큰 배열에 대해서는 퀵 정렬을 사용하는 방식이다.
• 평균적으로는 O(nlog(n))의 시간 복잡도이지만, 드물게 O(n^2)의 최악의 경우가 발생할 수 있다는 것은 퀵 정렬과 동일하다.

Collections.sort() : 컬렉션을 정렬하는 데 사용되는 방법이다. 합병 정렬을 기반으로 삽입 정렬을 결합한 Timsort를 사용한다.

• 합병 정렬의 최악의 경우와, 삽입 정렬의 최선의 경우를 얻을 수 있는 방법이라고 보면 되고, 시간복잡도는 O(n) ~ O(nlogn)을 보장할 수 있다.