[Java/Kotlin] List.sort()는 어떻게 정렬이 될까?

결론부터 말하고 시작하려 한다.

• List.sort()는 List의 데이터를 배열로 옮긴 뒤 정렬 이후 다시 리스트에 데이터를 옮긴다.
• 해당 정렬에 사용되는 알고리즘은 TimSort 이다.

이제 하나씩 까보자.

sort메소드는 매개변수로 전달되는 Comparator를 통해 값을 비교하여 오름차순으로 정렬하며 TimSort 알고리즘을 사용한다.

그렇다면 오름차순 정렬해주는 Comparator.naturalOrder() 메소드는 어떻게 구현이 되어 있을까....?

📏 Comparator.naturalOrder()

@Override
public int compare(Comparable<Object> c1,Comparable<Object> c2) {
	return c1.compareTo(c2);
}

• c1, c2를 비교하여 더 작은 값을 맨 앞으로 배치하는 방식 인 것 같다.
• compareTo() 메소드를 사용한다.
  그렇기에 해당 인터페이스 메소드를 가지고 있는 Comparable을 구현한 객체만 sort의 사용이 가능하다

📐 Comparator.reverseOrder()

 public int compare(Comparable<Object> c1,Comparable<Object> c2) {
	return c2.compareTo(c1);
}

너~무 당연하게도 내림차순 정렬은 compareTo() 메소드가 반대로 되어있다.
compareTo()를 부르는 오브젝트의 순서가 다르다!

🧐 내가 만든 Model class type이 Comparable인터페이스를 구현하지 않았다면 정렬이 불가할까?

public class Student {
       private int mAge;
       private String mName;
       
       public Student(int age, String name) {
              mAge = age;
              mName = name;
       }
       
       public int getAge() { return mAge; }
       
       public String getName() { return mName;  }
       
       public String toString() {
              return "age : " + mAge + " / name : " + mName;
       }
}

Student 클래스가 있다.
이를 정렬한다면?

list.sort(Comparator.naturalOrder());
or
list.sort(Comparator.reverseOrder());

아래와 같은 에러가 발생!

The method sort(Comparator<? super Student>) in the type List<Student> is not applicable for the arguments (Comparator<Comparable<? super Comparable<? super T>>>)

2가지 방법으로 해결이 가능하다.

1. sort메소드의 매개 변수로 model class type에 적용 가능한 Comparator를 전달한다.

2. model class에 Comparable을 implements 한 뒤 compareTo 메소드를 override 한다.

1️⃣ model class type의 데이터 비교를 위한 Comparator 전달

우린 단지 누가 더 큰지 비교할 때 Comparator를 사용한다.

student.sort(new Comparator<Student>() {
	@Override
    public int compare(Student arg0, Student arg1){
    	int age0 = arg0.getAge();
		int age1 = arg1.getAge();
        
		if(age0 == age1) return 0;
        else if(age0>age1) return 1;
        else return -1;
	}
}

리턴값

1 : 기준이 되는 데이터가 비교하는 데이터보다 큰 경우 양수를 리턴
0 : 기준이 되는 데이터가 비교하는 데이터와 같은 경우 0을 리턴
-1 : 기준이 되는 데이터가 비교하는 데이터보다 작은 경우 -1을 리턴
위의 리턴 방식은 오름차순 기준이다. 내림차순을 원한다면 1과 -1의 기준만 바꿔주면 된다.

2️⃣ model class의 Comparable 구현

public class Student implements Comparable<Student>{
       private int mAge;
       private String mName;
       
       public Student(int age, String name) {
              mAge = age;
              mName = name;
       }
       
       public int getAge() { return mAge; }
       
       public String getName() { return mName;  }
       
       public String toString() {
              return "age : " + mAge + " / name : " + mName;
       }

       @Override
       public int compareTo(Student arg0) {
              // TODO Auto-generated method stub
              int targetAge = arg0.getAge();
              if(mAge == targetAge) return 0;
              else if(mAge > targetAge) return 1;
              else return -1;
       }
}

기존 Model Class와 다른 점은 compareTo() 메소드를 오버라이드 했다.
아주 간단하게 정렬이 가능하다.