정렬

코딩 테스트에서의 정렬...

1. 직접 구현보다 내장 함수 사용
   • Arrays.sort() 또는 Collections.sort()로 대부분의 정렬 문제 해결 가능
2. 시간복잡도
   • Java의 내장 정렬은 Dual-Pivot QuickSort 또는 Timsort 기반
   • 평균 및 최악 시간복잡도: O(n log n)

1. Arrays.sort()

배열을 정렬할 때 사용되는 메서드

• 기본형 배열 (int[], char[], 등) → Dual-Pivot QuickSort 사용
• 객체 배열 (Integer[], String[], 등) → Timsort 사용
• 기본 정렬은 오름차순
• Comparator를 이용해 정렬 기준을 변경 가능

int[] numbers = {3, 1, 4, 1, 5};
Arrays.sort(numbers);  // 오름차순
System.out.println(Arrays.toString(numbers)); // [1, 1, 3, 4, 5]

 

2. Collections.sort()

List 타입(Collection 인터페이스 구현체)을 정렬할 때 사용됨

• 내부적으로 Timsort 사용
• 기본 정렬은 오름차순
• Comparator를 지정하여 다양한 방식으로 정렬 가능

List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5);
Collections.sort(numbers);
System.out.println(numbers); // [1, 1, 3, 4, 5]

 

3. 문자열 정렬

문자열을 정렬하려면 문자 배열로 변환 후 정렬

String text = "cdbae";
char[] chars = text.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
System.out.println(sorted); // "abcde"

 

4. 내림차순 정렬

1. 배열 (기본형) → Integer로 변환 필요

Integer[] arr = {3, 1, 4, 1, 5};
Arrays.sort(arr, Collections.reverseOrder());
System.out.println(Arrays.toString(arr)); // [5, 4, 3, 1, 1]

 

 

주의: 기본형 배열(int[])은 reverseOrder() 지원하지 않으므로, Integer[]로 변환해야 함

2. 리스트

List<Integer> list = Arrays.asList(3, 1, 4, 1, 5);
Collections.sort(list, Collections.reverseOrder());
System.out.println(list); // [5, 4, 3, 1, 1]

 

5. Comparator를 이용한 정렬 기준 변경

문자열 길이순 정렬

List<String> words = Arrays.asList("apple", "banana", "kiwi");
Collections.sort(words, Comparator.comparingInt(String::length));
System.out.println(words); // [kiwi, apple, banana]

 

사용자 정의 클래스 정렬

static class Pair {
    String name;
    int value;
    Pair(String name, int value) {
        this.name = name;
        this.value = value;
    }
    public String toString() {
        return "(" + name + ", " + value + ")";
    }
}

List<Pair> list = Arrays.asList(
    new Pair("apple", 3),
    new Pair("banana", 1),
    new Pair("cherry", 2)
);

Collections.sort(list, Comparator.comparingInt(p -> p.value));
System.out.println(list); // [(banana, 1), (cherry, 2), (apple, 3)]

 

람다 표현식

Collections.sort(list, (a, b) -> Integer.compare(a.value, b.value));

 

6. 정렬 활용

• 정렬을 통해 문제 구조를 단순화
• 최댓값, 최솟값, 특정 조건 필터링 문제
• 정렬 후 O(n) 탐색으로 문제를 빠르게 해결

시간복잡도 고려

데이터 크기	사용 가능 여부
10^4 이하	안전하게 사용 가능
10^5 ~ 10^6	O(n log n) 충분히 가능
10^7 이상	주의 필요, 정렬 한 번만 허용되는 문제 많음

주의할 점

• 입력 데이터가 이미 정렬되어 있을 수 있음
  • 예: 날짜 순, 점수 순 등
  • 이 경우 무분별한 재정렬은 오히려 문제를 왜곡할 수 있음