[Java] List 정렬에 대하여.

0.🚶들어가며

자바에서 List를 정렬하는 방법에 대해 찾아보다가 추가적인 몇몇 개념들을 살펴보게 되었습니다.

 

List를 정렬하는 방법, Comparable과 Comparator 인터페이스에 대해 글을 써보고 자바 List 정렬 방식인 tim sort에 대해 알아볼 수 있도록 잘 정리된 블로그 글을 소개해보도록 하겠습니다.

---

1.📚List를 정렬하는 방법

자바의 List를 정렬하는 방법에는 크게 두 가지가 있었습니다.

1) Collections 클래스의 static 메서드인 sort()를 사용하는 방법

사용 방법 먼저 살펴보도록 하겠습니다.

public class SortingDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("hello world");
        list.add("abcd");
        list.add("Kim");
        list.add("java");

        System.out.println("정렬 전 배열 : " + list);
        Collections.sort(list);
        System.out.println("정렬 후 배열 : " + list);
    }
}

# result

정렬 전 배열 : [hello world, abcd, Kim, java]
정렬 후 배열 : [Kim, abcd, hello world, java]

위 코드 10번 라인을 살펴보시면 Collections 클래스의 static 메서드인 sort를 사용했고 인자로는 list를 넘겨준 것을 알 수 있습니다.

 

결과는 자바의 String 정렬 방식인 대문자 우선, 알파벳 우선순위를 따라 잘 정렬되었네요!

 

그런데 조금 더 살펴봅시다. 아래 사진은 Collections 클래스의 sort 메서드 중 List 인터페이스를 인자로 받는 코드입니다.

Collections 클래스의 sort 내부 코드

Collections 클래스의 메서드를 이용해도 List 인터페이스의 sort 메서드를 사용하고 있네요. 사실상 두 번째 방법과 같은 방법을 이용한 것입니다. 그럼 두 번째 방법을 살펴보도록 하죠.

 

2) List 인터페이스의 default 메서드인 sort()를 사용하는 방법

사용 방법을 먼저 살펴보겠습니다.

public class SortingDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("hello world");
        list.add("abcd");
        list.add("Kim");
        list.add("java");
        
        System.out.println("정렬 전 배열 : " + list);
        list.sort(null);
        System.out.println("정렬 후 배열 : " + list);
    }
}

# result

정렬 전 배열 : [hello world, abcd, Kim, java]
정렬 후 배열 : [Kim, abcd, hello world, java]

첫 번째 방식과 같은 결과를 얻었고 정렬도 잘되었습니다. 당연한 이야기겠죠? 같은 메서드를 불렀으니까요! 이때 sort메서드에 null을 인자로 넘겼습니다. 이 부분에 대해 조금 더 살펴보도록 하겠습니다.

위 사진은 list 인터페이스의 default 메서드 sort 내부 코드입니다. 인자로 Comparator 객체를 요구하고 있네요! 제 코드에서는 해당 매개 변수 자리에 null을 인자로 넘겨준 것이고요. 또한 코드를 한 줄씩 살펴보면 Object 배열로 변환한 뒤 Arrays.sort 메서드를 호출한 것을 볼 수 있습니다. 

 

호출한 Arrays.sort 메서드가 무엇인지 알기 위해 타고 들어가 봅시다!

Arrays 클래스의 sort 메서드

위 사진은 Arrays 클래스의 sort 메서드입니다. 조건문을 보시면 정렬에는 LegacyMergeSort나 TimSort를 사용하는 것을 알 수 있는데요. LegacyMergeSort의 경우 API를 살펴보면 추후 제거될 예정이라고 합니다. 즉, 꼭 LegacyMergeSort 방식으로 해주세요라고 사용자가 요구하지 않는다면 TimSort 방식을 사용하는 것입니다. TimSort 방식에 대해서는 잘 정리된 글을 뒷 부분에 소개하겠습니다.

 

---

2.👬Comparable과 Comparator 인터페이스

위에서 Comparator에 대한 내용이 나왔습니다. sort 메서드에 비교 방식을 제공해주는 객체인데 비슷한 내용으로 Comparable이 있습니다. 두 가지 개념에 대해 알아보도록 하겠습니다.

 

앞서 살펴봤던 정렬 코드에서는 String을 담은 리스트를 정렬해보았습니다. 이에 다음 두 가지에 대한 질문이 생길 수도 있을 것 같습니다.

• String의 기본 정렬 기준은 어떤 코드가 결정하는 것일까?
• String을 다른 기준으로 정렬할 수는 없을까?

첫 번째 질문에 답할 수 있게 해주는 것이 바로 Comparable 인터페이스이고 두 번째 질문에 답할 수 있게 해주는 것이 바로 Comparator 인터페이스입니다.

 

# Comparable

위 사진은 String 클래스가 구현한 인터페이스를 보여줍니다. 우리가 찾던 Comparable 인터페이스가 있네요!

 

또 한 번 Comparable 인터페이스를 따라 들어가 봅시다.

public interface Comparable<T> {
    /*
   	 많은 내용의 주석...
    */
    public int compareTo(T o);
}

위 코드는 Comparable 인터페이스의 코드입니다. compareTo라는 메서드만을 구현하면 Comparable 인터페이스를 구현하는 것이죠.

String 클래스의 compareTo 구현 부분

위 사진은 String 클래스의 compareTo 메서드 구현 부분입니다. 정렬을 위해서는 비교 대상과의 대소 관계 기준이 필요합니다. 이러한 기준이 있어야 "정렬"이라는 행위를 할 수 있기 때문이죠. 이러한 기준을 compareTo 메서드에서 제공해주는 것입니다. "자신"과 "비교 대상 객체"를 적절한 기준으로 비교한 뒤 그 결과 값을 양수, 0, 음수로 리턴해주는 방식입니다.

 

실제로 정렬을 수행하는 메서드의 내부를 살펴보면 객체끼리의 대소 관계를 파악하기 위해 해당 객체에 구현되어 있는 compareTo 메서드를 호출합니다.

# Comparator

이제 비슷한 개념이라고 소개했던 Comparator를 알아보도록 하겠습니다. Comparable에 대해 알았고 이를 통해 정렬을 수행할 수 있다면 Comparator는 왜 필요한 것일까요?

 

Comparator는 위에서 살펴보았던 두 가지 질문 중 두 번째, "다른 기준"으로 정렬하고 싶은 경우 어떻게 해야 하는지에 대한 방법을 제공합니다.

 

우선 Comparator 인터페이스를 살펴보도록 합시다.

public interface Comparator<T> {
    int compare(T o1, T o2);
    
    /*
     코드와 주석들,,
    */
}

Comparator를 구현하기 위해서는 compare 메서드를 구현해야 합니다. 이 역시 Comparable과 메커니즘과 동일하나, 인자로 객체 두 개를 받는 것이 차이점입니다. 

 

두 객체를 적절한 기준을 가지고 비교하도록 구현하면 되고 리턴 값 역시 비교 결과에 따라 양수, 0, 음수로 내어주면 됩니다. 

 

이제 다시 처음 살펴보았던 정렬 코드를 살펴보겠습니다.

public class SortingDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("hello world");
        list.add("abcd");
        list.add("Kim");
        list.add("java");

        System.out.println("정렬 전 배열 : " + list);
        list.sort(null);
        System.out.println("정렬 후 배열 : " + list);
    }
}

# result

정렬 전 배열 : [hello world, abcd, Kim, java]
정렬 후 배열 : [Kim, abcd, hello world, java]

위와 같은 코드였는데요. 라인 10번을 보면 null이라고 넣어준 인자 자리가 바로 Comparator의 자리입니다. null을 넣었다는 뜻은 곧, String이 가지고 있는 기본 정렬 방식 즉, compareTo를 사용하여 정렬하겠다는 의미가 됩니다.

 

그렇다면 문자의 길이를 정렬 기준으로 삼고 싶다면 어떻게 해야 할지 살펴보겠습니다.

public class SortingDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("hello world");
        list.add("abcd");
        list.add("Kim");
        list.add("java");

        System.out.println("정렬 전 배열 : " + list);
        list.sort(new Comparator<String>(){
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });
        System.out.println("정렬 후 배열 : " + list);
    }
}

# result

정렬 전 배열 : [hello world, abcd, Kim, java]
정렬 후 배열 : [Kim, abcd, java, hello world]

이전과 다른 점을 확인하셨나요? list.sort 메서드 인자에 Comparator를 구현한 익명 객체를 넣어주었습니다. compare 메서드를 오버라이드하면서 길이를 기준으로 정렬하도록 return 값을 설정해준 것이죠. 이러한 방식을 통해 sort의 기준을 커스텀하여 정렬할 수 있게 되는 것입니다.

 

아래 사진은 sort 함수에 Comparator 객체를 인자로 넣어주었을 때 부르는 메서드 중 하나를 캡쳐한 사진입니다.

중간 if문을 보시면 c.compare 메서드를 부르고 있는 것을 볼 수 있는데요. c는 우리가 인자로 넣어준 Comparator 객체이고 우리가 커스텀해준 compare 함수를 통해 정렬을 수행하고 있음을 알 수 있습니다.

 

---

이렇게 정렬 기준을 제공해주는 Comparable 인터페이스와 Comparator 인터페이스를 살펴보았습니다. 두 인터페이스가 비슷한 기능을 제공해주어 헷갈릴 수 있지만 앞서 살펴보았던 두 가지 질문을 잘 생각해보시면 두 인터페이스의 용도 차이를 파악하실 수 있으실 것 같습니다.

• String의 기본 정렬 기준은 어떤 코드가 결정하는 것일까?
• String을 다른 기준으로 정렬할 수는 없을까?

---

3.🏄Tim sort

Tim sort 방식은 자바에서 List를 정렬할 때 사용하는 sort 방식입니다. 해당 내용을 제가 정리하기보다는 잘 정리해주신 블로그 글을 찾아 이를 소개하려 합니다. 궁금하시다면 아래 링크를 참고하여 살펴봐주세요!

자바 [JAVA] - 팀 정렬 (Tim Sort)

---

4. 💨나가며

이번 글은 자바 List 정렬에 대해 알아보다가 뱅뱅 돌아서 이것저것 알게 되어 작성하게 되었습니다. sort 메서드의 사용법만 알고 넘어갔다면 접하지 못했을 내용들이었던 것 같아 한 번 더 찾아보는 습관을 가지자 라는 마음가짐을 다시 되새길 수 있는 계기가 된 것 같습니다.  

 

긴 글 읽어주셔서 감사합니다.