컬렉션 프레임워크 - 정렬 (Comparable, Comparator)

cwchoiit 2024. 5. 19. 16:11

2024. 5. 19. 16:11

728x90

SMALL

참고자료:

김영한의 실전 자바 - 중급 2편 | 김영한 - 인프런

김영한 | 자바 제네릭과 컬렉션 프레임워크를 실무 중심으로 깊이있게 학습합니다. 자료 구조에 대한 기본기도 함께 학습합니다., 국내 개발 분야 누적 수강생 1위, 제대로 만든 김영한의 실전

www.inflearn.com

정렬

자료 구조에 저장된 데이터를 정렬하는 방법을 알아보자.

바로 예제를 살펴보자.

SortMain1

package org.example.collection.compare;

import java.util.Arrays;
import java.util.Comparator;

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

        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
    }
}

실행결과

[3, 2, 1]
[1, 2, 3]

Arrays.sort()를 사용하면 배열에 들어있는 데이터를 순서대로 정렬할 수 있다.

근데 반대로 1 - 2 - 3을 3 - 2 - 1로 내림차순으로 정렬하고 싶을 때도 있을거다. 그럴땐 어떻게 하면 될까?

이때, 비교자(Comparator)를 사용하면 된다. 비교 기준을 직접 제공할 수가 있다.

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

두 인수를 비교해서 결과 값을 반환하면 된다.

이 아래 3문장이 제일중요하다!!

음수를 반환한다면 첫번째 객체가 두번째 객체보다 앞에 와야함을 의미
두 값이 같으면 0
양수를 반환한다면 첫번째 객체가 두번째 객체보다 뒤에 와야함을 의미

Comparator는 음수를 반환하면 첫번째 인자를 더 작다고 판단하고 앞으로 보낸다. 그래서 오름차순으로 정렬하려고 한다면 다음과 같은 Comparator를 만들 수가 있다.

private static class AscComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 < o2 ? -1 : o1 == o2 ? 0 : 1; //오름차순
    }
}

o1이 o2보다 작다면 -1을 리턴한다. 같으면 0을, 작지도 같지도 않다면(더 크다면) 1을 리턴한다.

즉, 첫번째 인자가 두번째 인자보다 작으면 -1을 리턴한다는 것은 첫번째 인자를 더 작다고 판단하고 앞으로 보내는 오름차순 정렬이라고 볼 수 있다.

그럼, 반대로 생각해보자. 더 작은걸 뒤로 보내는 내림차순의 경우 첫번째 인자가 두번째 인자보다 작을 때 1을 리턴하면 된다.

private static class DescComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 < o2 ? 1 : o1 == o2 ? 0 : -1; //내림차순
    }
}

그래서 Comparator를 사용해서 Arrays.sort()를 사용하면 내가 원하는 정렬기준에 맞게 정렬할 수 있다.

package org.example.collection.compare;

import java.util.Arrays;
import java.util.Comparator;

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

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

        Arrays.sort(array, new AscComparator());
        System.out.println("오름차순 정렬= " + Arrays.toString(array));

        Arrays.sort(array, new DescComparator());
        System.out.println("내림차순 정렬= " + Arrays.toString(array));
    }

    private static class AscComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 < o2 ? -1 : o1 == o2 ? 0 : 1;
        }
    }

    private static class DescComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 < o2 ? 1 : o1 == o2 ? 0 : -1;
        }
    }
}

실행결과

[3, 2, 1]
[1, 2, 3]
오름차순 정렬= [1, 2, 3]
내림차순 정렬= [3, 2, 1]

근데 Comparator는 편의 메서드인 reversed()가 있다. 다음과 같이 사용하면 된다.

말 그대로 정렬을 반대로 한것이라고 보면 된다.

package org.example.collection.compare;

import java.util.Arrays;
import java.util.Comparator;

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

        Arrays.sort(array, new AscComparator().reversed());
        System.out.println("오름차순 정렬의 리버스(내림차순)= " + Arrays.toString(array));
    }

    private static class AscComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 < o2 ? -1 : o1 == o2 ? 0 : 1;
        }
    }
}

실행결과

오름차순 정렬의 리버스(내림차순)= [3, 2, 1]

근데 여기서 의문이 한가지 생긴다. 자바가 제공하는 Integer, String같은 객체를 제외하고 내가 직접 만든 객체(User, Team 등)도 정렬하고 싶을수 있다. 이럴땐 어떻게 할까? 내가 만든 객체이기 때문에 정렬을 할 때 내가 만든 객체의 두 인스턴스 중에 어떤 인스턴스가 더 큰지 알려줄 방법이 있어야 한다. 이때는 내가 만든 객체가 Comparable 인터페이스를 구현하면 된다. 이 인터페이스는 이름 그대로 비교 가능한, 비교할 수 있는 이라는 뜻으로 객체에 비교 기능을 추가해준다.

Comparable을 구현한 클래스

다음과 같은 클래스를 직접 만들었다고 생각해보자.

MyUser

package org.example.collection.compare;

public class 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 String toString() {
        return "MyUser{" +
                "id='" + id + '\'' +
                ", age=" + age +
                '}';
    }
}

이 클래스를 두고 나이 기준으로 정렬을 하고 싶으면 이 클래스가 Comparable을 구현하면 된다.

Comparable을 구현한 MyUser

package org.example.collection.compare;

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 String toString() {
        return "MyUser{" +
                "id='" + id + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(MyUser o) {
        // 오름차순
        return this.age < o.age ? -1 : this.age > o.age ? 1 : 0;
    }
}

그럼 별도의 Comparator없이도 정렬이 가능하다. 내가 정렬 기준을 제시해줬기 때문에.

SortMain2 (Comparable을 구현한 클래스를 정렬할때)

package org.example.collection.compare;

import java.util.Arrays;
import java.util.Comparator;

public class SortMain2 {
    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("나이 기준 오름차순 정렬 데이터");
        Arrays.sort(users); // MyUser 클래스가 Comparable을 구현한 경우
        System.out.println(Arrays.toString(users));
    }
}

실행결과

기본 데이터
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]
나이 기준 오름차순 정렬 데이터
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]

실행결과를 보니 나이 기준으로 오름차순 정렬이 됐다. 근데 꼭 이렇게 Comparable을 구현해야 할까? 아니다. 그럴 필요 없다. 그냥 두번째 인자에 나만의 Comparator를 던져주면된다.

SortMain2 (Comparable을 구현하지 않고 Comparator를 두번째 인자로 준 경우)

package org.example.collection.compare;

import java.util.Arrays;
import java.util.Comparator;

public class SortMain2 {
    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};

        Arrays.sort(users, Comparator.comparing(MyUser::getId)); // Comparable 구현이랑 상관없이, 직접 Comparator를 만든 경우
        System.out.println(Arrays.toString(users));
    }
}

두번째 인자로 Comparator를 람다 표현식의 익명 내부 클래스로 만들어서 던져줬다. (구현할 인터페이스가 딱 한개의 메서드만 가진 경우 익명 내부 클래스를 람다 표현식으로 작성할 수 있다)

참고로, 저 람다 표현식의 익명 내부 클래스는 이 클래스를 만든거랑 똑같다고 보면 된다.

package org.example.collection.compare;

import java.util.Comparator;

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

그래서 저 위의 코드를 바꾸면 이렇게 되는거다.

Arrays.sort(users, new IdComparator());

보면 MyUser가 가진 `id`를 기준으로 오름차순 정렬을 한다. 자바에서 문자를 오름차순 정렬하기 편하게 compareTo()를 구현해놨고 그거를 그대로 사용한다고 보면 된다. 그리고 만약 내가 `id`를 기준으로 내림차순 정렬하고 싶으면? 이렇게 쓰면 된다.

익명 내부 클래스를 람다 표현식으로 사용한 방식

Arrays.sort(users, Comparator.comparing(MyUser::getId).reversed());

직접 클래스를 만든 방식

Arrays.sort(users, new IdComparator().reversed());

중요

그래서, 중요한건 내가 만든 클래스를 정렬할 때 그 클래스가 Comparable을 구현한 클래스라면 그 클래스의 compareTo() 메서드를 가지고 정렬을 한다. 그게 아니라면 두번째 인자로 Comparator를 던져주어 내 입맛에 맞게 정렬한다. 둘 다 아니라면? 런타임 에러가 발생한다.

List와 정렬

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

SortMain3

package org.example.collection.compare;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

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);

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

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

        System.out.println("Comparable 기본 정렬");
        users.sort(null); // Comparator를 만들어서 넣어주는게 아니고 Comparable 구현한 그대로로 정렬한다는 뜻
        System.out.println(users);

        System.out.println("Comparator로 정렬");
        users.sort(Comparator.comparing(MyUser::getId)); // 첫번째 방법: 람다 익명 내부 클래스
        users.sort(new IdComparator()); // 두번째 방법: Comparator를 구현한 클래스
        System.out.println(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}]
Comparator로 정렬
[MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]

배열과 다르지 않다. Comparable을 구현한 클래스이고 그 정렬 기준 그대로를 사용한다면 List가 자체적으로 가지고 있는 sort() 메서드에 아무것도 넣지 않는다는 의미로 `null`을 넣으면 된다.

그게 아니라 내가 원하는 방식의 다른 정렬을 원한다면 Comparator를 직접 만들어 넣으면 된다.

근데 저 방법 말고 다른 방법이 하나 더 있긴한데 이건 권장되지 않고 저 방식대로 사용하면 된다. 알기는 알아야 하니까 작성하자면,

Collections.sort(users);
Collections.sort(users, new IdComparator());
Collections.sort(users, Comparator.comparing(MyUser::getId));

Collections를 사용해도 된다. 근데 보면 알겠지만 이런 `Warning` 문구를 보여준다.

Tree와 정렬

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

이렇게 생긴 이진 탐색 트리가 있다고 하면, 내가 여기에 6을 넣으려고 하면 아무곳에 넣을 수 있는게 아니라 정렬해서 6의 정확한 위치가 들어가야 한다. 이진 탐색 트리를 만족해야 하니까. (현재 노드를 기준으로 왼쪽은 무조건 더 작게, 오른쪽은 무조건 더 크게)

그 말은 TreeSet, TreeMap같은 자료 구조는 Comparable이나 Comparator가 필수이다.

SortMain4

package org.example.collection.compare;

import java.util.TreeSet;

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);

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

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

MyUser는 Comparable을 구현한 클래스이다. 그래서 TreeSet의 요소 타입으로 받아들일 수 있다. 그냥 트리에 데이터를 넣는순간 정렬이 된다. 진짜 그런지 실행결과를 보자.

실행결과

Comparable 기본 정렬
[MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]

알아서 나이의 오름차순(MyUser에서 구현한 정렬방식)으로 찍히는걸 볼 수 있다.

그럼 Comparable을 구현한 클래스가 아니라면 Comparator를 반드시 줘야 하는데 어떻게 주면 될까?

TreeSet<MyUser> treeSet2 = new TreeSet<>(new IdComparator());

이렇게 생성자에 Comparator를 넘겨주면 된다.

그래서 결론은 자바에서 트리 구조는 반드시 Comparable이나 Comparator가 필수라는 사실. 진짜 그런지 궁금한데 한번 해보자.

우선 MyUser가 Comparable을 구현한 클래스가 아니게 바꿨다.

MyUser (Comparable 구현 안 함)

package org.example.collection.compare;

public class 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 String toString() {
        return "MyUser{" +
                "id='" + id + '\'' +
                ", age=" + age +
                '}';
    }
}

그랬더니 벌써부터 경고문구가 보인다.

실행해보면? 런타임 에러가 발생한다.

결론

Integer, String 뿐 아니라 내가 직접 만든 클래스 또한 Array, List, Tree 자료구조에서 모두 내가 원하는 방식으로 정렬을 할 수 있다. 크게 두 가지 방법이 있다.

Comparable을 구현한 클래스이면 된다.
구현하지 않았어도 Comparator를 제공해주면 된다.

728x90

LIST

저작자표시

'JAVA의 가장 기본이 되는 내용' 카테고리의 다른 글

멀티스레드 Part.2 스레드 시작 (0)	2024.07.17
멀티스레드 Part.1 - 프로세스와 스레드 소개 (4)	2024.07.15
컬렉션 프레임워크 - 순회 (Iterable, Iterator) (0)	2024.05.19
컬렉션 프레임워크 - Deque (Stack, Queue) (0)	2024.05.18
컬렉션 프레임워크 - Map (0)	2024.05.16

programmer.cwchoiit