백준 2751번: 수 정렬하기 2

문제

https://www.acmicpc.net/problem/2751

---

코드

public static void main(String[] args) throws IOException {
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

        int amount = Integer.parseInt(br.readLine());

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < amount; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(list);

        StringBuilder sb = new StringBuilder();
        for (int i : list) {
            sb.append(i).append("\n");
        }

        System.out.println(sb);
    }
}

Arrays.sort(int[]) vs Arrays.sort(Object[]) and Collections.sort(List)

Arrays.sort(int[])

• DualPivotQuicksort라는 피벗을 두 개를 정해 구간을 3개로 하는 퀵소트를 사용한다.
• API에 따르면 이 때 평균 O(n log(n)) 성능을 제공하며 일반적으로 기존 (one-pivot) 쿽소트 보다 빠르다고 한다.
• 하지만 여전히 최악의 경우 O(n^2)인 것은 여전하다.

Arrays.sort(Object[]) and Collections.sort(List)

• java.util.Arrays.useLegacyMergeSort 설정에 따라 true면 legacyMergeSort를 통해 Merge sort로 정렬하고 false면 TimeSort를 통해 Tim sort로 정렬한다.
• 이 때 기본적으로 java.util.Arrays.useLegacyMergeSort 설정은 false로 지정되어 있다.
• Tim sort는 Insertion sort와 Merge sort를 결합하여 만든 정렬로 최선의 경우 O(n), 평균적으로 O(n log(n)), 최악의 경우 O(n log(n))의 성능을 제공한다.
• Tim sort에 대한 자세한 설명

java.util.Arrays.useLegacyMergeSort 확인

...

    static final class LegacyMergeSort {
        private static final boolean userRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
    }

...

• new sun.security.action.GetBooleanAction(“java.util.Arrays.useLegacyMergeSort”)).booleanValue(); 를 sysout으로 출력해보면 false가 return 되는 것을 확인할 수 있다.

---

결과

---