개발 학습 실습실

이 사이트의 실습은 자바스크립트를 켜야 움직입니다. 아래는 같은 내용을 글로 적은 것입니다.

공부 › Java › 컬렉션

정렬과 Comparator

정렬 순서는 누가 정하고, 빼서 비교하면 왜 틀리나

정렬은 "둘 가운데 어느 것이 앞인가"를 묻는 비교를 되풀이하는 일입니다. 그 답은 클래스가 스스로 정해 둘 수도 있고(Comparable), 정렬할 때 바깥에서 줄 수도 있습니다(Comparator).

실행으로 대조 · JDK 21에서 열여섯 가지 조합을 실행해 대조

이 실습에 나오는 개념

Comparable과 Comparator
객체의 순서를 정하는 두 가지 방법이다. Comparable은 클래스가 스스로 구현하는 인터페이스로, compareTo 메서드 하나에 그 클래스의 기본 순서를 정해 둔다. Comparator는 클래스 바깥에서 따로 만드는 비교 방법으로, 같은 객체들을 그때그때 다른 기준으로 정렬할 수 있게 해 준다. 둘 다 앞의 것이 먼저면 음수, 순서를 가릴 수 없으면 0, 나중이면 양수를 돌려준다. 두 수를 뺀 값을 그대로 돌려주면 오버플로로 부호가 뒤집힐 수 있으므로 Integer.compare나 Comparator.comparingInt를 쓴다.
안정 정렬
비교 결과가 같은(0인) 원소들의 원래 순서를 정렬한 뒤에도 그대로 지키는 정렬이다. 예를 들어 이름순으로 놓인 목록을 점수순으로 안정 정렬하면, 점수가 같은 사람끼리는 여전히 이름순이다. 자바에서 객체를 정렬하는 List.sort, Collections.sort, 객체 배열의 Arrays.sort는 안정 정렬이라고 문서에 적혀 있다. 그래서 여러 기준으로 차례차례 정렬하거나, 같은 값끼리의 순서가 바뀌면 안 되는 화면 목록을 정렬할 때 믿고 쓸 수 있다.
정수 오버플로
계산 결과가 그 타입이 담을 수 있는 범위를 넘어 엉뚱한 값이 되는 현상이다. 자바의 int는 -2147483648부터 2147483647까지 담을 수 있고, 이 범위를 넘으면 예외 없이 반대쪽 끝으로 넘어가 이어진다. 예를 들어 2147483647에 1을 더하면 -2147483648이 된다. 오류가 나지 않고 틀린 값이 조용히 쓰이므로 찾기 어렵다. 범위를 넘을 수 있는 계산에는 long을 쓰거나, 넘칠 때 예외를 던지는 Math.addExact 같은 메서드를 쓴다.
메서드 참조
이미 있는 메서드를 람다 대신 이름으로 가리키는 문법이다. String::length, System.out::println처럼 클래스(또는 객체)와 메서드 이름을 ::로 연결해 쓴다. 람다가 단순히 메서드 하나를 호출하기만 할 때 더 짧게 표현할 수 있다.
람다 표현식
이름 없는 함수를 간결하게 표현하는 문법으로 Java 8에서 도입되었다. (매개변수) -> 실행문 형태로 쓰며, 추상 메서드가 하나뿐인 함수형 인터페이스의 구현으로 사용된다. 동작(코드)을 값처럼 다른 메서드에 전달할 수 있게 해 준다.

이렇게 바꿔 보세요

처음 설정으로 실행하면

  1. List<Account> list = new ArrayList<>(List.of(...)): 계좌 다섯 개를 park, choi, kim, lee, han 순서로 담습니다. park와 kim의 잔액이 20억으로 같고, choi와 lee의 잔액이 -20억으로 같습니다.
  2. Comparator<Account> order = (a, b) -> a.balance() - b.balance(): 두 잔액을 뺀 값을 비교 결과로 씁니다. a가 작으면 음수, 같으면 0, 크면 양수가 나올 것이라고 생각하고 쓴 코드입니다.
  3. order.compare(park, choi): 2000000000 - (-2000000000)을 계산합니다. 수학으로는 4000000000이지만, int는 -2147483648부터 2147483647까지만 담을 수 있어 범위를 넘칩니다(오버플로). 실제로 나오는 값은 -294967296입니다. 음수이므로 park가 choi보다 앞에 놓입니다. 잔액이 더 큰 park를 앞에 놓으라는 틀린 답입니다.
  4. order.compare(park, kim): 두 잔액이 같으므로 결과는 0입니다. 0은 "순서를 가릴 수 없다"는 뜻이고, 정렬은 이런 둘의 순서를 바꾸지 않습니다.
  5. list.sort(order): order.compare를 여러 번 불러 가며 자리를 정합니다. 정렬된 순서는 park(20억), kim(20억), choi(-20억), lee(-20억), han(0)입니다. 잔액이 작은 것부터여야 하는데 그렇지 않습니다. 비교가 틀린 답을 냈기 때문입니다.
  6. System.out.println(list): 정렬된 목록을 출력합니다. 예외는 나지 않았습니다. 틀린 순서가 아무 경고 없이 나온 것입니다.

실행 결과

코드

record Account(String owner, int balance) implements Comparable<Account> {
    @Override
    public int compareTo(Account other) {        // 클래스가 스스로 정한 순서: 이름순
        return owner.compareTo(other.owner);
    }
}

List<Account> list = new ArrayList<>(List.of(
    new Account("park", 2_000_000_000), new Account("choi", -2_000_000_000),
    new Account("kim", 2_000_000_000), new Account("lee", -2_000_000_000),
    new Account("han", 0)));

Comparator<Account> order = (a, b) -> a.balance() - b.balance();   // 빼서 비교
System.out.println(order.compare(list.get(0), list.get(1)));   // park와 choi
System.out.println(order.compare(list.get(0), list.get(2)));   // park와 kim

list.sort(order);
System.out.println(list);

이 모형의 전제

열여섯 가지 조합의 정렬 결과, 두 번의 compare가 돌려준 값, 잔액 순서가 맞는지를 이 PC의 JDK 21에서 같은 코드를 실행한 결과와 대조했습니다. compare가 돌려주는 값 가운데 명세가 정한 것은 부호(음수, 0, 양수)뿐입니다. comparingInt의 1과 -1, 문자열 비교의 13과 5 같은 구체적인 숫자는 JDK 21에서 나온 값입니다. 빼서 비교하는 Comparator처럼 규칙을 어기는 비교를 주면 정렬 결과는 정렬 알고리즘의 내부 동작에 따라 달라집니다. 이 실습의 틀린 순서는 원소가 다섯 개일 때 JDK 21의 List.sort가 내는 결과입니다. List.sort의 문서에는 Comparator가 규약을 어긴 것이 발견되면 IllegalArgumentException을 던질 수 있다고 적혀 있습니다(이 경우는 실행해 보지 않았습니다). 정렬 과정의 비교는 여러 번 일어나지만, 화면에는 그 가운데 두 번만 따로 실행해 보여 줍니다.

앞 실습: 순회 중 삭제 · 다음 실습: 람다와 함수형 인터페이스

이 실습에 나오는 개념

이 실습에서 보는 것

설정

코드


      
    


    

      
그림

      

      

    


    

      

      

      

    


  


  

    

      
실행 비교

      

      

    

    

      
이렇게 바꿔 보세요