정렬
데이터를 특정 기준에 따라 일정한 순서로 재배열하는 알고리즘입니다.
왜 필요한가?
정렬되지 않은 배열: [5, 2, 8, 1, 9, 3]
→ 특정 값 찾기 = O(n)
→ 중복 검사 = O(n²)
→ 최솟값/최댓값 = O(n)
정렬된 배열: [1, 2, 3, 5, 8, 9]
→ 특정 값 찾기 = O(log n) O (이진 탐색)
→ 중복 검사 = O(n) O (인접 비교)
→ 최솟값/최댓값 = O(1) O (양 끝)
정렬 자체가 목적인 경우는 적습니다. 대부분 정렬을 전제로 다른 알고리즘이 쉬워지기 때문에 정렬을 합니다.
분류 기준
| 기준 | 구분 |
|---|---|
| 비교 방식 | 비교 기반(Ω(n log n)) vs 비교 비기반(O(n) 가능) |
| 안정성 | 같은 키 원소의 입력 순서 유지 여부 |
| 메모리 | in-place(추가 공간 거의 없음) vs 보조 배열 필요 |
비교 기반 정렬은 어떤 알고리즘이라도 n log n보다 빠를 수 없다는 것이 증명되어 있습니다(결정 트리 분석). 더 빠르려면 입력에 대한 추가 가정(값 범위가 작다 등)이 필요합니다.
주요 정렬 비교
| 알고리즘 | 평균 | 최악 | 공간 | 안정 | in-place |
|---|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | O | O |
| 선택 정렬 | O(n²) | O(n²) | O(1) | X | O |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | O | O |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | O | X |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | X | O |
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | X | O |
| 계수 정렬 | O(n+k) | O(n+k) | O(n+k) | O | X |
| 기수 정렬 | O(d(n+k)) | O(d(n+k)) | O(n+k) | O | X |
| 팀소트 | O(n log n) | O(n log n) | O(n) | O | X |
Java 표준 라이브러리
| 메서드 | 대상 | 내부 알고리즘 | 안정 |
|---|---|---|---|
| Arrays.sort | int[] 원시 타입 | dual-pivot 퀵소트 | X |
| Arrays.sort | Object[] 객체 타입 | 팀소트 | O |
| Collections.sort | List | 팀소트 | O |
| List.sort | List (Java 8+ 권장) | 팀소트 | O |
| Stream.sorted | 모든 컬렉션 / 배열 | 팀소트 | O |
| Arrays.parallelSort | int[], Object[] (대용량) | 병렬 팀소트 | O (객체 타입) |
원시 타입 vs 객체 타입:
int[] → 퀵소트 (속도 우선, 안정성 불필요)
Integer[] / Object[] → 팀소트 (안정성 보장)
실전에서는 직접 짜지 않고 표준 정렬에 Comparator만 잘 정의해 사용합니다.
정렬을 활용하는 패턴
코딩테스트에서는 정렬 자체보다 정렬 후 활용이 훨씬 더 많이 나옵니다.
| 패턴 | 예시 |
|---|---|
| 정렬 후 인접 비교 | 중복 검사, 가장 가까운 두 수, 접두사 검사, 구간 겹침 |
| 정렬 + 이진 탐색 | 특정 값 존재 여부, lower/upper bound |
| 정렬 + 투 포인터 | 두 수의 합, 세 수의 합 |
| 정렬 + 그리디 | 회의실 배정, 작업 스케줄링 |
| 좌표 압축 | 큰 값 범위를 작은 인덱스로 매핑 |
| 커스텀 비교자 | 다중 기준 정렬, 객체 정렬 |
핵심 정리
정렬은 데이터를 순서대로 재배열하는 알고리즘이며, 그 자체보다 정렬을 전제로 다른 알고리즘이 쉬워지기 때문에 의미가 큽니다. 비교 기반 정렬은 Ω(n log n) 하한이 있고, 실전에서는 퀵 정렬 / 병합 정렬 / 힙 정렬이 핵심입니다. 표준 라이브러리는 이미 잘 튜닝된 하이브리드(팀소트, 인트로소트)를 쓰므로 직접 구현하지 말고 비교 함수만 잘 정의해 쓰며, N 제한과 안정성·메모리 요구에 따라 적절한 정렬을 고릅니다.