[Java] Arrays.sort() 알아보기

알고리즘 문제를 풀다가 정렬하는 과정에서 선택정렬을 사용하여 정렬을 하였으나, 시간초과가 발생하였습니다.

대안으로 Arrays.sort(arr)를 사용하였고 시간초과가 발생하지 않는 것을 확인하였습니다.

이번 포스팅에서는 Arrays.sort()의 사용법과 시간복잡도에 대해 알아보겠습니다.

 

사용법

---

int[] arr = {5,3,1,2,4};
Arrays.sort(arr);
//arr -> 1,2,3,4,5

Arrays.sort(arr)은 arr 배열을 오름차순으로 정렬합니다. 반대로 내림차순의 경우 기본타입인 int, double, char, float를 사용하는 게 아닌 Wrapper Class인 Double, String, Integer 등을 사용해야 합니다.

Integer[] arr = {5,3,1,2,4};
Arrays.sort(arr, Collections.reverseOrder());
// arr->5,4,3,2,1

 

시간복잡도

---

Arrays.sort()는 기본타입의 오름차순인 경우 아래와 같이 DualPivotQuicksort.sort()를 호출하는 것을 확인할 수 있습니다.

퀵 정렬의 경우 시간 복잡도는 평균적으로 O(nlogn)이고, 최악의 경우 O(n^2)를 가집니다.

배열 타입이 int인 경우

배열 타입이 double인 경우

다음은 Wrapper class인 경우를 확인해 보겠습니다. 아래와 같이 mergeSort를 호출하는 것을 확인할 수 있습니다.

병합 정렬의 시간 복잡도는 O(nlogn)이고, 최악의 경우도 마찬가지로 O(nlogn)을 가집니다.

 

2차원 배열 정렬

---

Arrays.sort()를 사용하여 2차원 배열 정렬도 가능합니다.

int[][] arr = new int[][]{{1,4},{3,5},{0,6},{5,7},{3,8},{4,8},{5,9},{2,13}};

Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[0]-o2[0]; // 첫번째 숫자 기준 오름차순 {0,6}{1,4}{2,13}{3,5}{3,8}{4,8}{5,7}{5,9}
        //return o2[0]-o1[0]; // 첫번째 숫자 기준 내림차순 {5,7}{5,9}{4,8}{3,5}{3,8}{2,13}{1,4}{0,6}
        //return o1[1]-o2[1]; // 두번째 숫자 기준 오름차순 {1,4}{3,5}{0,6}{5,7}{3,8}{4,8}{5,9}{2,13}
        //return o2[1]-o1[1]; // 두번째 숫자 기준 내림차순 {2,13}{5,9}{3,8}{4,8}{5,7}{0,6}{3,5}{1,4}
    }
});

이를 더 응용시키면 예를 들어, 두 번째 숫자 기준 오름차순이며 만약 값이 같은 경우 첫 번째 숫자 기준 오름차순으로 정렬하는 방법은 아래와 같습니다.

Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        if(o1[1] == o2[1])
            return o1[0] - o2[0];
        return o1[1] - o2[1];
    }
});

 

참고자료

---

https://bangu4.tistory.com/287