정렬1 - Comparable, Comparator

데이터를 정렬하는 방법을 알아보자.

 

package collection.compare;

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

}

 

실행 결과

[3, 2, 1]
기본 정렬 후
[1, 2, 3]

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

원래 3,2,1 순서로 데이터가 들어있었는데, 정렬 후에는 1,2,3의 순서로 데이터가 정렬된 것을 확인할 수 있다.

 

정렬 알고리즘

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

• 먼저 가장 왼쪽에 있는 데이터와 그 다음 데이터를 비교한다.
• 3과 2를 비교했을 때 3이 더 크기 때문에 둘을 교환한다.

• 다음 차례의 둘을 비교한다.
• 3과 1을 비교했을 때 3이 더 크기 때문에 둘을 교환한다.
• 이렇게 처음부터 끝까지 비교하면 마지막 항목은 가장 큰 값이 된다. 여기서는 3이다.

• 처음으로 돌아와 다시 비교를 시작한다.
• 2와 1을 비교했을 때 2가 더 크기 때문에 둘을 교환한다.
• 최종적으로 1,2,3으로 정렬된다.

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

 

비교자 - Comparator

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

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

 

 

 

package collection.compare;

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

        Arrays.sort(array, new AscComparator().reversed());
        System.out.println("AscComparator.reversed" + Arrays.toString(array));
    }

    static class DescComparator implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1 = " + o1 + " o2= " + o2);
            return(o1<o2) ? -1 : ((o1==o2) ? 0 :1) * -1;
        }
    }

    static class AscComparator implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1 = " + o1 + " o2= " + o2);
            return(o1<o2) ? -1 : ((o1==o2) ? 0 :1);
        }
    }

}

 

실행 결과

[3, 2, 1]
Comparator 비교
o1 = 2 o2= 3
o1 = 1 o2= 2
AssComparator : [1, 2, 3]
o1 = 2 o2= 1
o1 = 3 o2= 2
DescComparator : [3, 2, 1]
o1 = 3 o2= 2
o1 = 2 o2= 1
AscComparator.reversed[3, 2, 1]

 

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

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

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

정렬을 반대로

new AscComparator().reversed()

• 정렬을 반대로 하고 싶으면 reversed() 메서드를 사용하면 된다. 이렇게 하면 비교의 결과를 반대로 변경한다. 앞서 설명한 -1을 곱한 것과 같은 결과가 나온다.

 

비교자(Comparator)를 사용하면 정렬의 기준을 자유롭게 변경할 수 있다.