백준 문제풀이 2751번 수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

코드

public class Main {
    public static void main(String[] args) {
        //수정렬하기2
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        int n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            list.add(sc.nextInt());
        }

        Collections.sort(list);

        for (Integer i : list) {
            sb.append(i).append('\n');
        }
        System.out.println(sb);
    }
}

풀이

https://st-lab.tistory.com/106 참조
Arrays.sort로 풀면 시간초과가 난다.
Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용하는데 최악의 경우 시간복잡도는 O(n2)가 걸리게 된다.
매우 많은 시간이 걸리게 된다는 것임.
그래서 최악의 경우에도 O(nlogn) 을 보장하거나 혹은, O(n) 에 가까운 정렬 알고리즘을 사용해야 한다.
그중 하나는 Collections.sort() 를 쓰는 방법이다. Collections.sort()는 Timsort이다. 이 정렬의 경우 합병 및 삽입정렬 알고리즘을 사용한다고 한다.