Java :: ArrayList 정렬을 위한 sort 메소드 파해치기

개요

필자는 모 사이트에서 프로그래밍 문제를 해결하던 중, 입력된 데이터를 오름차순으로 정렬하여 리턴하라는 문제가 있어 해당 메소드에 대해 알아보았다.

List에는 데이터 정렬을 위한 sort라는 메소드가 존제한다.

물론 List를 상속받는 ArrayList 또한 이 sort 메소드를 사용할 수 있다.

이를 통해 편리하게 오름차순 혹은 내림차순으로 데이터 정렬이 가능하다.

---

Comparable를 구현(implements)하는 클레스

정렬을 하기 위해서는 리스트 속 데이터 간 크기 비교가 가능해야한다.

즉, 리스트 안에 들어있는 오브젝트의 수치화가 가능해야 한다는 것.

Java에서는 비교가 가능한(수치화가 가능한) 오브젝트들은 Comparable<T> 인터페이스를 implements 하고있으며 우리가 사용하는 대부분의 데이터 클레스가 속한다.

어떤 클레스가 비교 가능한지 궁금하다면 https://docs.oracle.com/javase/10/docs/api/java/lang/Comparable.html 의 All known Implementing classes 를 참고하면 된다.

(이번 예제에 사용될 Integer는 하이라이트 처리 해두었다.)

이 인터페이스 안에는 int compareTo(T a) 라는 단 하나의 interface 메소드만 존제한다.

이 메소드에 대한 설명은 아래와 같으며 리턴값을 3가지로 분류하고 있다.

• parameter보다 작은 경우 음수를 리턴
• parameter와 같은 경우 0을 리턴
• parameter보다 큰 경우 양수를 리턴

int compareTo(T o)

Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y. (This implies that x.compareTo(y) must throw an exception iff y.compareTo(x) throws an exception.)

The implementor must also ensure that the relation is transitive: (x.compareTo(y) > 0 && y.compareTo(z) > 0) implies x.compareTo(z) > 0.

Finally, the implementor must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero, or positive, respectively.

Parameters:

o - the object to be compared.

Returns:

a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

Throws:

NullPointerException - if the specified object is null

ClassCastException - if the specified object's type prevents it from being compared to this object.

interface 메소드는 implements하는 클레스에서 반드시 구현해야 하기 때문에 Comparable<T>를 implements하는 모든 클레스들은 해당 메소드를 구현해야한다.

예를들어 자주 사용되는 java.lang.Integer 클레스는 Comparable<Integer>를 implements하고 있으며, 아래와 같이 compareTo 메소드가 구현되어 있다.

58: public final class Integer extends Number implements Comparable<Integer>

....

512: /**

513: * Compare two Integers numerically by comparing their <code>int</code>

514: * values. The result is positive if the first is greater, negative if the

515: * second is greater, and 0 if the two are equal.

516: *

517: * @param i the Integer to compare

518: * @return the comparison

519: * @since 1.2

520: */

521: public int compareTo(Integer i)

522: {

523:      if (value == i.value)

524:      return 0;

525:      // Returns just -1 or 1 on inequality; doing math might overflow.

526:      return value > i.value ? 1 : -1;

527: }

결과적으로 sort메소드는 Comparable<T> 인터페이스를 구현한 오브젝트 타입의 ArrayList라면 특별한 구현이 없이도 가능하다.

---

List.sort() 메소드의 활용

java doc에서는 sort 메소드를 아래와 같이 설명한다.

default void sort(Comparator<? super E> c)

Sorts this list according to the order induced by the specified Comparator. The sort is stable: this method must not reorder equal elements.

All elements in this list must be mutually comparable using the specified comparator (that is, c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the list).

If the specified comparator is null then all elements in this list must implement the Comparable interface and the elements' natural ordering should be used.

This list must be modifiable, but need not be resizable.

Implementation Requirements:

The default implementation obtains an array containing all elements in this list, sorts the array, and iterates over this list resetting each element from the corresponding position in the array. (This avoids the n² log(n) performance that would result from attempting to sort a linked list in place.)

Implementation Note:

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.

The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techniques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

Parameters:

c - the Comparator used to compare list elements. A null value indicates that the elements' natural ordering should be used

Throws:

ClassCastException - if the list contains elements that are not mutually comparable using the specified comparator

UnsupportedOperationException - if the list's list-iterator does not support the set operation

IllegalArgumentException - (optional) if the comparator is found to violate the Comparator contract

Since:

1.8

여기서 재미있는 내용이 나오는데 List의 데이터를 배열로 옮긴 뒤 정렬한 뒤에 다시 리스트에 데이터를 옮긴다는 것과,

해당 정렬에 사용되는 알고리즘은 TimSort라는 이름을 가지고 있으며 이는 Tim Peters라는 개발자가 구현했다는 내용이다.

결국 누군가가 만들어놓은 좋은 효율의 알고리즘을 가져와 재사용 한 것이다.

다시 본론으로 돌아와서 sort 메소드는 parameter로 받는 Comparator를 통해 리스트 안의 데이터를 비교하며 오름차순으로 정렬한다.

만약 리스트의 데이터 오브젝트가 Comparable을 implements한 오브젝트라면 null값을 입력해 오름차순으로 정렬할 수 있다.

ArrayList<Integer> list = new ArrayList<>();

list.add(1);

list.add(4);

list.add(6);

list.add(2);

list.add(5);

System.out.println("정렬 전  : " + list.toString());

list.sort(null);

System.out.println("오름차순 : " + list.toString());

정렬 전  : [1, 4, 6, 2, 5]

오름차순 : [1, 2, 4, 5, 6]

sort메소드에 대한 java doc에서는 list.sort(null)은 list.sort(Comparator.naturalOrder()) 와 같다고 설명하고 있으며,

실제로 결과도 같게 나온다.

ArrayList<Integer> list = new ArrayList<>();

list.add(1);

list.add(4);

list.add(6);

list.add(2);

list.add(5);

System.out.println("정렬 전  : " + list.toString());

list.sort(Comparator.naturalOrder());

System.out.println("오름차순 : " + list.toString());

정렬 전  : [1, 4, 6, 2, 5]

오름차순 : [1, 2, 4, 5, 6]

반대로 내림차순은 Comparator.reverseOrder() 메소드를 통해 리턴받은 comparator를 통해 가능하다. 

단, List 데이터 오브젝트가 Comparable을 implements하는 경우에만 해당된다.

ArrayList<Integer> list = new ArrayList<>();

list.add(1);

list.add(4);

list.add(6);

list.add(2);

list.add(5);

System.out.println("정렬 전  : " + list.toString());

list.sort(Comparator.naturalOrder());

System.out.println("오름차순 : " + list.toString());

list.sort(Comparator.reverseOrder());

System.out.println("내림차순 : " + list.toString());

정렬 전  : [1, 4, 6, 2, 5]

오름차순 : [1, 2, 4, 5, 6]

내림차순 : [6, 5, 4, 2, 1]

---

sort 메소드 파해치기

우리는 지금까지 java doc을 살펴보며 sort 메소드는 메게변수로 전달되는 Comparator를 통해 값을 비교해 오름차순으로 정렬하며 TimSort 알고리즘을 사용한다는 것을 알았다.

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

궁금하면 직접 까봐야 직성이 풀리기 때문에 판도라의 상자를 열어보았다.

(jdk설치경로/src.zip에 자바 소스코드가 모두 들어있다.)

        @Override

        public int compare(Comparable<Object> c1, Comparable<Object> c2) {

            return c1.compareTo(c2);

        }

해당 메소드는 java/utill/Comparators.java 파일에 들어있다.

간단한 형태이며, c1과 c2를 비교해 작은 값을 맨 앞으로 배치시키는 듯 하다.

여기서 한가지 알 수 있는 사실은 compareTo 메소드를 활용한다는 점이다.

그렇기 때문에 해당 interface 메소드를 가지고있는 interface class인 Comparable을 implements한 object만 sort의 사용이 가능하다는 것이다.

그렇다면, 반대로 내림차순으로 list를 정렬해주는 Comparator.reserveOrder() 의 원형은 어떨까?

        public int compare(Comparable<Object> c1, Comparable<Object> c2) {

            return c2.compareTo(c1);

        }

naturalOrder()와 비슷하지만 compareTo 메소드를 부르는 오브젝트의 순서가 다르다.

이는 오름차순에서 사용된 "크다"의 의미가 "작다"로 바뀐다는 것이며, 큰수가 맨 앞으로 오도록 정렬하게 해준다.

---

Model class type의 ArrayList 정렬하기

sort 메소드 파해치기를 통해 List의 type이 Comparable을 implements한 경우에만 sort 메소드의 오름차순 혹은 내림차순 정렬 기능을 사용할 수 있다는 것을 살펴보았다.

그렇다면, 내가 만든 model class type의  list는 정렬이 불가능할까?

정답은 "가능하다".

우선 아래와 같은 model class가 있다고 가정해보자.

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

왜 이런 에러가 발생하는지 모르겠다면 위의 내용들을 다시 한번 읽어보길 바란다.

-

이런 상황에서 sort메소드를 사용하기 위한 방법은 2가지다.

1. sort 메소드의 메게변수로 model class type에 적용 가능한 Comparator를 전달한다.
   
   
2. model class에 Comparable을 implements한 뒤 compareTo 메소드를 override한다.

우선 첫번째 방법부터 살펴보자.

---

방법1. model class type의 데이터 비교를 위한 Comparator 전달

sort 메소드는 메게변수를 기다리며 늘 외치고 있다.

"누가 더 큰지 알려줘! 정렬은 내가 할게!"

그렇다. 우리는 단지 누가 더 큰지 비교할 때 사용할 비교기(Comparator)만 전달해주면 된다. 바로 아래처럼.

students.sort(new Comparator<Student>() {

       @Override

       public int compare(Student arg0, Student arg1) {

              // TODO Auto-generated method stub

              int age0 = arg0.getAge();

              int age1 = arg1.getAge();

              

              if(age0 == age1) return 0;

              else if(age0 > age1) return 1;

              else return -1;

       }

});

여기에는 3가지 규칙이 있다.

• 기준이 되는 데이터가 비교하는 데이터보다 큰 경우 양수를 리턴
• 기준이 되는 데이터가 비교하는 데이터와 같은 경우 0을 리턴
• 기준이 되는 데이터가 비교하는 데이터보다 작은 경우 음수를 리턴

이러한 구현을 통해 리스트 안의 데이터를 오름차순으로 정렬할 수 있다.

내림차순으로 정렬하고 싶은 경우에는 비교 순서를 바꿔주면 된다.

예제)

public static void main(String[] args) {

       // TODO Auto-generated method stub

       List<Student> students = new ArrayList<>();

       students.add(new Student(16, "Jack"));

       students.add(new Student(12, "Merry"));

       students.add(new Student(18, "Simuel"));

       System.out.println("정렬 전");

       

       for (int i = 0; i < students.size(); i++)

              System.out.println(students.get(i).toString());

       // 오름차순 정렬

       students.sort(new Comparator<Student>() {

              @Override

              public int compare(Student arg0, Student arg1) {

                     // TODO Auto-generated method stub

                     int age0 = arg0.getAge();

                     int age1 = arg1.getAge();

                     if (age0 == age1)

                           return 0;

                     else if (age0 > age1)

                           return 1;

                     else

                           return -1;

              }

       });

       

       System.out.println("오름차순 정렬");

       for (int i = 0; i < students.size(); i++)

              System.out.println(students.get(i).toString());

       

       // 내림차순 정렬

       students.sort(new Comparator<Student>() {

              @Override

              public int compare(Student arg0, Student arg1) {

                     // TODO Auto-generated method stub

                     int age0 = arg0.getAge();

                     int age1 = arg1.getAge();

                     if (age0 == age1)

                           return 0;

                     else if (age1 > age0)

                           return 1;

                     else

                           return -1;

              }

       });

       

       System.out.println("내림차순 정렬");

       for (int i = 0; i < students.size(); i++)

              System.out.println(students.get(i).toString());

}

결과)

정렬 전

age : 16 / name : Jack

age : 12 / name : Merry

age : 18 / name : Simuel

오름차순 정렬

age : 12 / name : Merry

age : 16 / name : Jack

age : 18 / name : Simuel

내림차순 정렬

age : 18 / name : Simuel

age : 16 / name : Jack

age : 12 / name : Merry

---

방법2. model class의 Comparable 구현(Implements)

이번에 소개할 방법은 model class에 Comparable을 구현하여

list.sort(Comparator.naturalOrder());

or

list.sort(Comparator.reverseOrder());

위 메소드 사용이 가능하도록 하는 방법이다.

아래와 같이 Model class에 Comparable을 Implements 해주면 된다.

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;

       }

}

기존 모델 클레스와 다른 점은 compareTo 메소드를 오버라이드 했다는 점이다.

이렇게 수정된 모델 타입의 리스트는 간단히 정렬이 가능하다.

예제 )

public static void main(String[] args) {

       // TODO Auto-generated method stub

       List<Student> students = new ArrayList<>();

       students.add(new Student(16, "Jack"));

       students.add(new Student(12, "Merry"));

       students.add(new Student(18, "Simuel"));

       System.out.println("정렬 전");

       

       for (int i = 0; i < students.size(); i++)

              System.out.println(students.get(i).toString());

       // 오름차순 정렬

       students.sort(Comparator.naturalOrder());

       

       System.out.println("오름차순 정렬");

       for (int i = 0; i < students.size(); i++)

              System.out.println(students.get(i).toString());

       

       // 내림차순 정렬

       students.sort(Comparator.reverseOrder());

       

       System.out.println("내림차순 정렬");

       for (int i = 0; i < students.size(); i++)

              System.out.println(students.get(i).toString());

}

출력 )

정렬 전

age : 16 / name : Jack

age : 12 / name : Merry

age : 18 / name : Simuel

오름차순 정렬

age : 12 / name : Merry

age : 16 / name : Jack

age : 18 / name : Simuel

내림차순 정렬

age : 18 / name : Simuel

age : 16 / name : Jack

age : 12 / name : Merry

---

마치며

자세하고 정확하게 설명을 하다보니 본의 아니게 글이 길어지고 많은 내용을 적게 되었습니다.

틀린 부분이나 질문이 있다면 아래 댓글에 남겨주시면 성실히 답변해드리도록 할게요.

어떻게 보면 정말 간단한 함수이지만, 이렇게 들어다보면 재미있는 연관성들이 있다는 것을 나누고 싶었습니다!

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

github