import java.io.BufferedReader;  
import java.io.BufferedWriter;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.io.OutputStreamWriter;  
import java.util.ArrayList;  
import java.util.Collections;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int N = Integer.parseInt(st.nextToken());  
  
        ArrayList<Integer> A = new ArrayList<>();  
        st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < N; i++) {  
            A.add(Integer.parseInt(st.nextToken()));  
        }  
  
        Collections.sort(A, (i1, i2) -> i1 - i2);  
  
        for (int a : A) {  
            bw.write(String.format("%d ", a));  
        }  
        bw.flush();  
    }  
}

💬 들어가며

안녕하세요, 헤일러입니다.

저는 과거에 C++언어로 문제 풀이를 했었는데, Java/Kotlin으로만 코딩 테스트를 보는 기업들이 많다 보니 Java로 문제 풀이하는 연습을 시작하고 있습니다.

한달 전부터 Java로 풀기 시작했는데요. C++에서 사용하던 자료구조와 메서드 기능들이 그대로 동작할 것을 기대하면서 사용하고 있는 Java 기능들이 많습니다.

그 중에 하나가 정렬입니다.

C++의 #include<algorithm> 헤더의 sort()는 Intro Sort(Quick Sort + Heap Sort + Insertion Sort 하이브리드 방식)를 사용해 최악에도 O(nlogn)을 보장한다는 것을 알고 있습니다.

Java에서는 Collections.sort()는 O(nlogn)을 보장하고, Arrays.sort()는 최악에 O(n^2)라기에 Arrays.sort()는 사용하지 말아야지! 정도로만 인지하고 Collections.sort()를 사용하고 있었는데 이 둘의 차이가 실제로 어떻게 다른지 궁금해서 내부를 잠시 들여다보았습니다.

✅ Collections.sort(List<T>) 동작 방식

// Collections.java
public static <T extends Comparable<? super T>> void sort(List<T> list) {  
    list.sort(null);  
}

// List.java
default void sort(Comparator<? super E> c) {  
    Object[] a = this.toArray();  
    Arrays.sort(a, (Comparator) c);  
    ListIterator<E> i = this.listIterator();  
    for (Object e : a) {  
        i.next();  
        i.set((E) e);  
    }  
}

// Arrays.java
public static <T> void sort(T[] a, Comparator<? super T> c) {  
    if (c == null) {  
        sort(a);  
    } else {  
        if (LegacyMergeSort.userRequested)  
            legacyMergeSort(a, c);  
        else  
            TimSort.sort(a, 0, a.length, c, null, 0, 0);  
    }  
}

• 내부적으로 List.sort()를 호출하고, List.toArray()를 호출한 후 Arrays.sort()를 사용하고, 정렬된 배열을 다시 List에 복사하는 방식으로 동작합니다.
• Arrays.sort(T[] a, Comparator<? super T> c)를 호출하는데 이 때 Arrays.sort(T[] a, Comparator<? super T> c)는 Tim Sort 알고리즘을 사용합니다.

📌 Tim Sort
Merge Sort에서 구간을 분할했을 때, 이미 정렬된 구간만 Inserstion Sort로 빠르게 처리하고, 나머지 부분에서는 Merge Sort 방식으로 합치는 방식입니다.
Merge Sort를 기반으로 동작하므로 최악에도 시간복잡도 O(nlogn)을 보장합니다.

✅ Arrays.sort() 동작 방식

Arrays.sort(int[]) 등 primitive 타입 배열인 경우

// Arrays.java
public static void sort(int[] a) {  
    DualPivotQuicksort.sort(a, 0, 0, a.length);  
}
...
public static void sort(long[] a) {  
    DualPivotQuicksort.sort(a, 0, 0, a.length);  
}
...
public static void sort(double[] a) {  
    DualPivotQuicksort.sort(a, 0, 0, a.length);  
}

• primitive 타입 배열의 정렬은 Dual-Pivot Quick Sort 알고리즘을 사용합니다.

📌 Dual-Pivot Quick Sort
Quick Sort에서 pivot 선택 전략과 파티션을 분할하는 방식을 최적화한 정렬 알고리즘입니다.
Quick Sort에서는 1개의 pivot을 선택해 2개의 파티션으로 분할하고, Dual-Pivot Quick Sort에서는 2개의 pivot을 선택해 3개의 파티션으로 분할합니다.
Dual-Pivot Quick Sort도 Quick Sort와 마찬가지로 평균 O(nlogn)의 시간이 걸리지만, 최악의 케이스에서 O(n^2)으로 동작합니다.
알고리즘 문제에서는 시간복잡도 최악을 저격하는 테스트 케이스를 (대부분 당연히) 포함하므로 사용에 주의를 기울여야 합니다. 네, 사용하면 시간초과를 받는다는 말입니다.

Arrays.sort(Object[])

// Arrays.java
public static void sort(Object[] a) {  
    if (LegacyMergeSort.userRequested)  
        legacyMergeSort(a);  
    else  
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);  
}

• primitive 타입이 아닌 객체 타입의 배열은 Collection.sort()와 마찬가지로 Tim Sort로 동작합니다.
• 정렬할 배열 원소 타입이 Comparable 인터페이스를 구현하고 있거나, sort() 함수의 두번째 인자에 Comparator 객체를 전달해주어야 합니다.

✅ 정리

• Tim Sort는 최악에도 시간복잡도 O(nlogn)을 보장합니다.

• Dual-Pivot Quick Sort는 최악에 시간복잡도 O(n^2)으로 동작합니다.

• Collections.sort(List<T>)는 항상 Tim Sort로 동작합니다.

• Arrays.sort()는 인자가 primitive 타입이면 Dual-Pivot Quick Sort, 객체 타입이면 Tim Sort로 동작합니다.

int[] distance = new int[10];
...

Arrays.sort(distance); // Dual-Pivot Quick Sort

public class Edge implements Comparable<Edge> {  
    int u;  
    int v;  
    int w;  
  
    public Edge(int u, int v, int w) {  
        this.u = u;  
        this.v = v;  
        this.w = w;  
    }  
  
    @Override  
    public int compareTo(Edge o) {  
        return this.w - o.w;  
    }  
}
...

Edge[] edges = new Edge[10];
...

Arrays.sort(edges); // Tim Sort