java에서 Arrays.sort()는 어떻게 동작할까?

이태현·2024년 1월 15일

Java 정렬

java로 알고리즘을 풀던 중, 무심코 사용하던 Arrays.sort()의 동작 방식과 시간 복잡도를 모르고 사용하고 있어, 이번 기회에 정리하고자 합니다.

Arrays.sort() 종류

기본적으로 sort()함수는 2가지 형식으로 구분할 수 있습니다.

배열을 전달하여 배열 전체를 sorting
배열과 시작 인덱스, 종료 인덱스를 전달하여, 특정 구간만 sorting

sorting가능한 배열은 int, byte, char, long, float, short, double, Object, T가 있습니다.

Primitive 타입

앞의 7가지 타입은 primitive 타입을 나타내며, sorting할 경우, 오름차순으로 정렬됩니다.

int[] intArr = {3,1,2,4,6,5};
Arrays.sort(intArr); // 1번

char[] charArr = {'a', 'd', 'b', 'e', 'c'};
Arrays.sort(charArr); // 2번

String[] strArr = {"ab", "a", "cde", "ca"};
Arrays.sort(strArr); // 3번

Arrays.sort(intArr, 2, 5); // 4번

실행 결과
[3, 1, 2, 4, 6, 5] -> [3, 1, 2, 4, 6, 5] // 1번
[a, d, b, e, c] -> [a, b, c, d, e] // 2번
[ab, a, cde, ca] -> [a, ab, ca, cde] // 3번
[3, 1, 2, 4, 6, 5] -> [3, 1, 2, 4, 6, 5] // 4번

Object 타입

Object 타입은 배열 내의 모든 Object가 서로 묵시적 형변환이 가능한 경우에만 sorting이 가능합니다. 만약 비교가 불가능한 Object가 포함된 배열인 경우, java.lang.ClassCastException이 발생합니다.

이해를 돕기 위해, 다음과 같이 MyClass를 정의하고, sort()를 호출해보겠습니다.

public static class MyClass implements Comparable {
    int x;

    public MyClass(int x){
        this.x = x;
    }

    @Override
    public String toString() {
        return Integer.toString(x);
    }

    @Override
    public int compareTo(Object o) {
        return this.x - ((MyClass)o).x;
    }
}

MyClass[] myclasses = new MyClass[4];
myclasses[0] = new MyClass(4);
myclasses[1] = new MyClass(1);
myclasses[2] = new MyClass(7);
myclasses[3] = new MyClass(2);
        
Arrays.sort(myclasses);

myClasses라는 배열을 생성한 후에 myClasses만 sort()에 전달하면,
public static void sort(Object[] a) 함수가 호출되게 됩니다.

주의 : 이때 MyClass내부에서 Comparable를 구현하지 않으면 java.lang.ClassCastException예외가 발생합니다.
따라서 Comparable 인터페이스를 구현하고, compareTo메소드까지 구현하여, 객체간의 대소비교가 가능하도록 하여야 합니다.

compareTo()에서 리턴값이 양수인 경우, 현재 객체와 비교 객체의 자리를 바꾸게 됩니다.
따라서 예시에서 return this.x - ((MyClass)o).x;의 경우, 현재 객체가 더 큰 값일 때 양수를 리턴하고, 자리를 바꾸기 때문에 오름차순 정렬이 수행됩니다.

T 타입(제너릭)

T 제네릭타입의 경우, 반드시 2번째 인자로 Comparator<T>를 구현한 클래스를 같이 전달해주어야합니다. 제너릭 타입의 경우, 객체의 대소를 비교할 수 있는 방법이 없기 때문에 개발자가 직접, T객체의 대소비교를 하는 compare(T t1, T t2)를 직접 구현해주어야 합니다.

다음과 같이 MyComparator를 구현해 보겠습니다.

    static class MyComparator implements Comparator<MyClass> {
        @Override
        public int compare(MyClass o1, MyClass o2) {
            return o2.x - o1.x; // 내림차순 정렬
        }
    }

사용할 때는 Arrays.sort(myclasses, new MyComparator());처럼 사용할 수 있습니다.
또는 다음과 같이 익명 구현 클래스를 통해 작성할 수도 있습니다.

Arrays.sort(myclasses, new Comparator<MyClass>() {
    @Override
    public int compare(MyClass o1, MyClass o2) {
        return o2.x - o1.x;
    }
});