본문 바로가기
복습

[Java 복습] 정렬 Comparable, Comparator

쌈뽕코딩 2024. 5. 20. 21:31

목차

  • 정렬
  • 정렬 알고리즘
  • 비교자 Comparator
  • 비교자 Comparable
  • 직접 만든 객체의 정렬
  • Tree 구조와 정렬

 

정렬

public class SortMain1 {

    public static void main(String[] args) {
        Integer[] array = {3, 2, 1};
        System.out.println(Arrays.toString(array));

        System.out.println("기본 정렬 후");
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
    }
}
[3, 2, 1]
기본 정렬 후
[1, 2, 3]

 

 

정렬 알고리즘


정렬은 대략 다음과 같은 방식으로 이루어진다.

 

 

  • 먼저 가장 왼쪽에 있는 데이터와 그 다음 데이터를 비교한다.
  • 3과 2를 비교했을 때 3이 더 크기 때문에 둘을 교환한다.

 

  • 다음 차례의 둘을 비교한다.
  • 3과 1를 비교했을 때 3이 더 크기 때문에 둘을 교환한다.
  • 이렇게 처음부터 끝까지 비교하면 마지막 항목은 가장 큰 값이 된다. 여기서는 3이다.

 

  • 처음으로 돌아와서 다시 비교를 시작한다.
  • 2와 1을 비교했을 때 2가 더 크기 때문에 둘을 교환한다.
  • 최종적으로 1, 2, 3으로 정렬된다.

지금 설명한 정렬은 가장 단순한 정렬의 예시이다. 실제로는 정렬 성능을 높이기 위한 다양한 정렬 알고리즘이 존재한다.

자바는 초기에는 퀵소트를 사용했다가 지금은 데이터가 작을 때(32개 이하)는 듀얼 피벗 퀵소트(Dual-Pivot QuickSort)를 사용하고, 데이터가 많을 때는 팀소트(TimSort)를 사용한다. 이런 알고리즘은 평균 O(n log n)의 성능을 제공한다.

 

비교자 - Comparator

그런데 정렬을 할 때 1, 2, 3 순서가 아니라 반대로 3, 2, 1로 정렬하고 싶다면 어떻게 해야할까?
이때는 비교자( Comparator )를 사용하면 된다. 이름 그대로 두 값을 비교할 때 비교 기준을 직접 제공할 수 있다.

public interface Comparator<T> {
 int compare(T o1, T o2);
}
  • 인수를 비교해서 결과 값을 반환하면 된다.
  • 첫 번째 인수가 더 작으면 음수, 예( -1 )
  • 두 값이 같으면 0
  • 첫 번째 인수가 더 크면 양수, 예( 1 )
public class SortMain2 {

    public static void main(String[] args) {
        Integer[] array = {3, 2, 1};

        System.out.println(Arrays.toString(array));
        System.out.println("Comparator 비교");

        Arrays.sort(array, new AscComparator());
        System.out.println("AscComparator: " + Arrays.toString(array));

        Arrays.sort(array, new DscComparator());
        System.out.println("DscComparator: " + Arrays.toString(array));

        Arrays.sort(array, new AscComparator().reversed()); //DescComparator와 같다.
        System.out.println("AscComparator.reversed(): " + Arrays.toString(array));
    }

    static class AscComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1 = " + o1 + " o2 = " + o2);
            return (o1 < o2) ? -1 : (o1 == o2) ? 0 : 1;
        }
    }

    static class DscComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1 = " + o1 + " o2 = " + o2);
            return (o1 < o2) ? -1 : ((o1 == o2) ? 0 : 1) * -1;
        }
    }
}
[3, 2, 1]
Comparator 비교
o1=2 o2=3
o1=1 o2=2
AscComparator:[1, 2, 3]
o1=2 o2=1
o1=3 o2=2
DescComparator:[3, 2, 1]
o1=3 o2=2
o1=2 o2=1
AscComparator.reversed:[3, 2, 1]

 

  • Arrays.sort() 를 사용할 때 비교자( Comparator )를 넘겨주면 알고리즘에서 어떤 값이 더 큰지 두 값을 비교할 때, 비교자를 사용한다.
  • 비교자( Comparator )를 사용하면 정렬의 기준을 자유롭게 변경할 수 있다.

 

 

Comparable


자바가 기본으로 제공하는 Integer , String 같은 객체를 제외하고 MyUser 와 같이 직접 만든 객체를 정렬하려면 어떻게 해야 할까? 내가 만든 객체이기 때문에 정렬을 할 때 내가 만든 두 객체 중에 어떤 객체가 더 큰지 알려줄 방법이 있어야 한다.
이때는 Comparable 인터페이스를 구현하면 된다. 이 인터페이스는 이름 그대로 비교 가능한, 비교할 수 있는 이라는 뜻으로, 객체에 비교 기능을 추가해 준다.

public interface Comparable<T> {
    public int compareTo(T o);
}
  • 자기 자신과 인수로 넘어온 객체를 비교해서 반환하면 된다.
  • 현재 객체가 인수로 주어진 객체보다 더 작으면 음수, 예( -1 )
  • 두 객체의 크기가 같으면 0
  • 현재 객체가 인수로 주어진 객체보다 더 크면 양수, 예( 1 )
public class MyUser implements Comparable<MyUser>{

    private String id;
    private int age;

    public MyUser(String id, int age) {
        this.id = id;
        this.age = age;
    }

    public String getId() {
        return id;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(MyUser o) {

        return (this.age < o.age) ? -1 : (this.age == o.age ? 0 : 1);
    }

    @Override
    public String toString() {
        return "MyUser{" +
                "id='" + id + '\'' +
                ", age=" + age +
                '}';
    }
}

 

  • MyUser 가 Comparable 인터페이스를 구현한 것을 확인할 수 있다.
  • compareTo() 구현을 보면 여기서는 정렬의 기준을 나이( age )로 정했다.
  • MyUser 클래스의 기본 정렬 방식을 나이 오름차순으로 정한 것이다.
  • Comparable 을 통해 구현한 순서를 자연 순서(Natural Ordering)라 한다.
public class SortMain3 {

    public static void main(String[] args) {

        MyUser myUser1 = new MyUser("a", 30);
        MyUser myUser2 = new MyUser("b", 20);
        MyUser myUser3 = new MyUser("c", 10);

        MyUser[] users = {myUser1, myUser2, myUser3};

        System.out.println("기본 데이터");
        System.out.println(Arrays.toString(users));

        System.out.println("Comparable 기본 정렬");
        Arrays.sort(users);
        System.out.println(Arrays.toString(users));
    }
}
기본 데이터
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
Comparable 기본 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]

 

Arrays.sort(array)

기본 정렬을 시도한다. 이때는 객체가 스스로 가지고 있는 Comparable 인터페이스를 사용해서 비교한다.
MyUser 가 구현한 대로 나이( age ) 오름차순으로 정렬된 것을 확인할 수 있다. MyUser 의 자연적인 순서를 사용했다.

 

 

다른 방식으로 정렬

 

만약 객체가 가지고 있는 Comparable 기본 정렬이 아니라 다른 정렬을 사용하고 싶다면 어떻게 해야할까?
나이가 아니라 아이디로 비교하는 예제를 추가로 만들어보자.

public class IdComparator implements Comparator<MyUser> {
    @Override
    public int compare(MyUser o1, MyUser o2) {
        return o1.getId().compareTo(o2.getId());
    }
}
public class SortMain3 {

    public static void main(String[] args) {

        MyUser myUser1 = new MyUser("a", 30);
        MyUser myUser2 = new MyUser("b", 20);
        MyUser myUser3 = new MyUser("c", 10);

        MyUser[] users = {myUser1, myUser2, myUser3};

        System.out.println("기본 데이터");
        System.out.println(Arrays.toString(users));

        System.out.println("Comparable 기본 정렬");
        Arrays.sort(users);
        System.out.println(Arrays.toString(users));
        
        // 추가
        System.out.println("IdComparator 정렬");
        Arrays.sort(users, new IdComparator());
        System.out.println(Arrays.toString(users));

        System.out.println("IdComparator().reversed() 정렬");
        Arrays.sort(users, new IdComparator().reversed());
        System.out.println(Arrays.toString(users));
    }
}
기본 데이터
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
Comparable 기본 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]
IdComparator 정렬
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
IdComparator().reversed() 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]

 

Arrays.sort(array, Comparator)

기본 정렬이 아니라 정렬 방식을 지정하고 싶다면 Arrays.sort 의 인수로 비교자(Comparator)를 만들어서 넘겨주면 된다. 이렇게 비교자를 따로 전달하면 객체가 기본으로 가지고 있는 Comparable 을 무시하고, 별도로 전달한 비교자를 사용해서 정렬한다. 여기서는 기본으로 나이를 기준으로 정렬하지만, 아이디로 정렬하고 싶다면 IdComparator 를 넘겨주면 된다.
결과를 보면 아이디( id ) 순으로 정렬된 것을 확인 할 수 있다.

 

 

주의!
만약 Comparable 도 구현하지 않고, Comparator 도 제공하지 않으면 런타임 오류가 발생한다.

Comparator 가 없으니, 객체가 가지고 있는 기본 정렬을 사용해야 한다. 이때 Comparable 을 사용한다. 

그런데 Comparable 을 찾는데 없으니, 예외가 발생한다.

 

 

Comparable, Comparator 정리
객체의 기본 정렬 방법은 객체에 Comparable 를 구현해서 정의한다. 이렇게 하면 객체는 이름 그대로 비교할 수 있는
객체가 되고 기본 정렬 방법을 가진다. 그런데 기본 정렬 외에 다른 정렬 방법을 사용해야 하는 경우 비교자(Comparator)를 별도로 구현해서 정렬 메서드에 전달하면 된다. 이 경우 전달한 Comparator 가 항상 우선권을 가진다.
자바가 제공하는 Integer , String 같은 기본 객체들은 대부분 Comparable 을 구현해 두었다.

 

 

 

정렬은 배열 뿐만 아니라 순서가 있는 List 같은 자료 구조에도 사용할 수 있다.

public class SortMain4 {
    public static void main(String[] args) {

        MyUser myUser1 = new MyUser("a", 30);
        MyUser myUser2 = new MyUser("b", 20);
        MyUser myUser3 = new MyUser("c", 10);

        List<MyUser> list = new LinkedList<>();
        list.add(myUser1);
        list.add(myUser2);
        list.add(myUser3);

        System.out.println("기본 데이터");
        System.out.println(list);

        System.out.println("Comparable 기본 정렬");
        list.sort(null);
        //Collections.sort(list);
        System.out.println(list);

        System.out.println("IdComparator 정렬");
        list.sort(new IdComparator());
        //Collections.sort(list, new IdComparator());
        System.out.println(list);
    }
}
기본 데이터
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
Comparable 기본 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]
IdComparator 정렬
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]

 

 

Collections.sort(list)
리스트는 순서가 있는 컬렉션이므로 정렬할 수 있다.이 메서드를 사용하면 기본 정렬이 적용된다.
하지만 이 방식보다는 객체 스스로 정렬 메서드를 가지고 있는 list.sort() 사용을 더 권장한다. 

참고로 둘의 결과는 같다.

 


list.sort(null)
별도의 비교자가 없으므로 Comparable 로 비교해서 정렬한다.
자연적인 순서로 비교한다.자바 1.8 부터 사용

 


Collections.sort(list, new IdComparator())
별도의 비교자로 비교하고 싶다면 다음 인자에 비교자를 넘기면 된다.
하지만 이 방식보다는 객체 스스로 정렬 메서드를 가지고 있는 list.sort() 사용을 더 권장한다. 

참고로 둘의 결과는 같다.

 


list.sort(new IdComparator())
전달한 비교자로 비교한다. 자바 1.8 부터 사용

 

 

 

Tree 구조와 정렬


TreeSet 과 같은 이진 탐색 트리 구조는 데이터를 보관할 때, 데이터를 정렬하면서 보관한다. 

따라서 정렬 기준을 제공하는 것이 필수다.

 

이진 탐색 트리는 데이터를 저장할 때 왼쪽 노드에 저장해야 할 지, 오른쪽 노드에 저장해야 할 지 비교가 필요하다.
따라서 TreeSet , TreeMap 은 Comparable 또는 Comparator 가 필수이다.

public class SortMain5 {
    public static void main(String[] args) {

        MyUser myUser1 = new MyUser("a", 30);
        MyUser myUser2 = new MyUser("b", 20);
        MyUser myUser3 = new MyUser("c", 10);

        Set<MyUser> treeSet1 = new TreeSet<>();
        treeSet1.add(myUser1);
        treeSet1.add(myUser2);
        treeSet1.add(myUser3);

        System.out.println("Comparable 기본 정렬");
        System.out.println(treeSet1);

        TreeSet<MyUser> treeSet2 = new TreeSet<>(new IdComparator());
        treeSet2.add(myUser1);
        treeSet2.add(myUser2);
        treeSet2.add(myUser3);

        System.out.println("IdComparator 정렬");
        System.out.println(treeSet2);
    }
}
Comparable 기본 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]
IdComparator 정렬
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]

 

 

주의!
만약 Comparable 도 구현하지 않고, Comparator 도 제공하지 않으면  런타임 오류가 발생한다.

 

 

정리
자바의 정렬 알고리즘은 매우 복잡하고, 또 거의 완성형에 가깝다.
자바는 개발자가 복잡한 정렬 알고리즘은 신경 쓰지 않으면서 정렬의 기준만 간단히 변경할 수 있도록, 

정렬의 기준을 Comparable , Comparator 인터페이스를 통해 추상화해 두었다.
객체의 정렬이 필요한 경우 Comparable 을 통해 기본 자연 순서를 제공하자. 

자연 순서 외에 다른 정렬 기준이 추가로 필요하면 Comparator 를 제공하자.

'복습' 카테고리의 다른 글

[Java 복습] 컬렉션 프레임워크 전체 정리  (0) 2024.05.20
[Java 복습] 컬렉션 유틸  (0) 2024.05.20
[Java 복습] 직접 구현해보는 Iterator  (0) 2024.05.20
[Java 복습] Deque와 Stack, Queue 자료 구조  (0) 2024.05.19
[Java 복습] Map 개념 뿌시기  (0) 2024.05.19

'복습' Related Articles

티스토리툴바