Arrays.sort()와 Collections.sort()

알고리즘 정렬 문제를 푸는 중 sort() 시간복잡도의 차이가 있다는 것을 알게되었다.

보통 배열 정렬할 때 Arrays.sort() List,Set등 정렬을할 때 Collections.sort()를 사용한다.

같은 sort 메서드지만 내부에서는 다른 정렬법을 사용한다.

	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균 : O(nlog(n)) / 최악 : O(n^2)
Collections.sort()	TimeSort (삽입정렬과 합병정렬을 결합한 정렬)	평균, 최악 : O(nlog(n))

Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용한다. 평균 시간복잡도가 O(nlogn) 이고 매우 빠른 알고리즘인 것은 맞다. 하지만 최악의 경우 시간복잡도는 O(n2) 이라는 점을 인지해야한다.

Collections.sort() 은 Timsort이다. Timsort 의 경우 합병 및 삽입정렬 알고리즘을 사용한다. 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm 이라고 하는데, 합병정렬(Merge Sort)의 경우 최선, 최악 모두 O(nlogn)  을 보장하고. 삽입정렬(Insertion sort)의 경우 최선의 경우는 O(n) , 최악의 경우는 O(n2) 이다. 그리고 두 정렬 모두 안정 정렬(stable sort)이기 때문에 Timsort를 hybrid stable sorting algorithm이라고도 한다.

boj2751 문제를 예로 들어보자

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class boj_2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i = 0; i < N; i++){
            arr.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(arr);
        for(int i = 0; i < arr.size(); i++){
            bw.write(arr.get(i)+"\n");
        }
        bw.flush();
    }
}

Collections.sort를 썻을 경우 시간초과로 틀리는 일이 없다 하지만 Arrays.sort를 썻을 경우 아래와 같이 시간초과로 실패하게된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i = 0; i < N; i++){
            arr.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(arr);
        for(int i = 0; i < arr.size(); i++){
            System.out.println(arr.get(i));
        }
    }
}

따라서 최악이 O(nlog(n))의 시간복잡도를 갖는 Collections.sort()가 더 빠르다.