Java - 데이터 정렬 1 (Comparable,Comparator)

배열에 있는 데이터를 정렬 해보자

import java.util.Arrays;

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

        System.out.println("기본 정렬 후");
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
    }
}

 

 

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

 

정렬 알고리즘

정렬은 대략 다음과 같은 방식으로 이루어진다.

먼저 가장 왼쪽에 있는 데이터와 그 다음 데이터를 비교한다.

3과 2를 비교 했을 때, 3이 더 크기 때문에 둘을 교환한다.

 

다음 차례의 둘을 비교한다.

3과 1를 비교했을 때, 3이 더 크기 때문에 교환한다.

이렇게 처음부터 끝까지 비교하면 마지막 항목은 가장 큰 값이 된다. 여기서는 3이다.

 

처음으로 돌아와서 다시 비교를 한다.

2와 1를 비교했을 때 2가 더 크기 때문에 둘을 교환한다.

최종적으로 1,2,3 으로 정렬된다.

 

 

위의 예시는 정렬를 이해햐기 위해 가장 간단한 예시를 설명한 것이다.

실제로는 정렬 성능을 높이기 위한 다양한 정렬 알고리즘이 존재한다. 자바는 초기에는 퀵소트를 사용했다가 지금은 데이터가 작을 때는(32개이하) 듀얼 피벗 퀵소트(Dual-PivotQuickSort)를 사용하고, 데이터가 많을 때는 팀소트(TimSort)를 사용한다. 이런 알고리즘은 평균 O(n log n)의 성능을 제공한다.

 

 

비교자 - Comparator

그런데 정렬을 할 때 1,2,3 순서가 아니라 반대로 3,2,1로 정렬하고 싶다면 어떻게 해야할까?

이때는 비교자(Comparator)을 사용하면 된다.  이름 그대로 두 값을 비교할 때 비교 기준을 직접 제공할 수 있다.

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

 

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

• 첫 번째 인수가 더 작으면 음수, 예 -1
• 두 값이 같으면 0
• 첫 번째 인수가 더 크면 양수 , 예 1

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

public class SortMain2 {
    public static void main(String[] args) {
        Integer[] array = {3, 2, 1};
        System.out.println(Arrays.toString(array));
        System.out.println("Comparator 비교");
        Arrays.sort(array,new AscComparator());
        System.out.println("AscComparator : " + Arrays.toString(array));

        Arrays.sort(array,new DescComparator());
        System.out.println("DescComparator : " + Arrays.toString(array));
        //DescComparator과 같다.
        Arrays.sort(array, new AscComparator().reversed());
        System.out.println("AscComparator.revered : " + Arrays.toString(array));
        
    }


    static class AscComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1 = " + o1);
            System.out.println("o2 = " + o2);
            if(o1 < o2) {
                return -1;
            } else if(o1 == o2) {
                return 0;
            } else {
                return 1;
            }
        }
    }
    static class DescComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1 = " + o1);
            System.out.println("o2 = " + o2);

            if(o1 < o2) {
                return 1;
            } else if (o1 == o2) {
                return 0;
            } else {
                return -1;
            }
        }
    }

}

 

 

 

Arrays.sort()를 사용할 때 비교자(Comparator)를 넘겨주면 알고리즘에서 어떤 값이 더 값을 비교할 때, 비교자를 사용한다.

 

Arrays.sort(array, new AscComparator())
Arrays.sort(array, new DescComparator())

 

o AscComparator를 사용하면 오름차순으로 정렬된다.

o DescComparator를 사용하면 숫자가 점점 내려가는 내림차순으로 정렬된다. 왜냐하면 DescComparator구현의 마지막에 -1을 곱해주기 때문에 이렇게하면 양수는 음수로, 음수는 양수로 반환된다. 쉽게 이야기해서 계산의 결과가 반대로 된다. 따라서 정렬의 결과도 반대가 된다.