STUDY NOTE · 개념 정리
정렬 알고리즘 비교 정리: 버블·선택·삽입·병합·퀵·힙 정렬과 안정 정렬
Algorithm
정렬 알고리즘은 시간 복잡도, 추가 메모리, 안정성 세 가지로 비교한다. O(n²) 정렬(버블·선택·삽입)은 단순하지만 느리고, O(n log n) 정렬(병합·퀵·힙)이 실전용이다. 비교 기반 정렬은 O(n log n)보다 빠를 수 없다.
1. 한눈에 비교
| 알고리즘 | 최선 | 평균 | 최악 | 추가 공간 | 안정 |
| 버블 정렬 | O(n)* | O(n²) | O(n²) | O(1) | O |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | O(1) | X |
| 삽입 정렬 | O(n) | O(n²) | O(n²) | O(1) | O |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | O(n) | O |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n²) | O(log n) (재귀 스택) | X |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) | O(1) | X |
| 계수 정렬 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | O (구현에 따라) |
* 버블 정렬의 O(n)은 한 바퀴 동안 교환이 없으면 멈추는 최적화를 넣었을 때다. 계수 정렬의 k는 값의 범위다.
2. O(n²) 정렬
| 알고리즘 | 아이디어 | 특징 |
| 버블 | 이웃한 두 원소를 비교해 큰 것을 뒤로 보냄. 한 바퀴마다 가장 큰 값이 끝에 확정 | 교환이 많아 가장 느린 편 |
| 선택 | 남은 구간에서 최솟값을 찾아 맨 앞과 교환 | 교환 횟수가 최대 n-1번으로 적음, 멀리 떨어진 원소끼리 교환해 불안정 |
| 삽입 | 앞쪽 정렬된 구간에 현재 원소를 알맞은 자리에 끼워 넣음 | 거의 정렬된 데이터에서 O(n)에 가까움, 작은 배열에서 빠름 |
void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) { // 큰 원소를 한 칸씩 뒤로
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
a[j] > key처럼 같은 값은 넘어가지 않으므로 삽입 정렬은 안정 정렬이다. 조건을 >=로 바꾸면 안정성이 깨진다.
3. O(n log n) 정렬
| 알고리즘 | 아이디어 | 장점 | 단점 |
| 병합 정렬 | 반으로 나눠 각각 정렬한 뒤 두 정렬된 배열을 합침 (분할 정복) | 항상 O(n log n), 안정 | O(n) 추가 메모리 |
| 퀵 정렬 | 피벗을 골라 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누고 재귀 | 평균적으로 가장 빠름, 제자리 정렬 | 피벗이 계속 한쪽 끝이면 O(n²), 불안정 |
| 힙 정렬 | 배열로 최대 힙을 만들고 루트(최댓값)를 끝으로 보내기를 반복 | 항상 O(n log n), 추가 메모리 O(1) | 캐시 효율이 낮아 실제로는 퀵보다 느린 편, 불안정 |
void mergeSort(int[] a, int[] tmp, int lo, int hi) { // [lo, hi)
if (hi - lo < 2) return;
int mid = (lo + hi) >>> 1;
mergeSort(a, tmp, lo, mid);
mergeSort(a, tmp, mid, hi);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
System.arraycopy(tmp, lo, a, lo, hi - lo);
}
병합할 때 값이 같으면 왼쪽(a[i] <= a[j])을 먼저 넣기 때문에 원래 순서가 유지된다.
4. 퀵 정렬의 최악과 피벗 선택
피벗을 항상 첫 번째(또는 마지막) 원소로 고르면, 이미 정렬된 배열에서 매번 한쪽이 비어 분할이 n번 일어나 O(n²)이 된다. 그래서 실제 구현은 무작위 피벗이나 처음·중간·끝 중 중앙값(median-of-three)을 쓰고, 작은 구간에서는 삽입 정렬로 바꾸는 식으로 보완한다.
5. 안정 정렬이 왜 중요한가
안정 정렬은 정렬 기준이 같은 원소들의 원래 순서를 유지한다. 여러 기준으로 차례로 정렬할 때 의미가 생긴다.
정렬 전 (주문일 순): [A: 배송중, 5/1] [B: 완료, 5/2] [C: 배송중, 5/3]
상태로 안정 정렬: [A: 배송중, 5/1] [C: 배송중, 5/3] [B: 완료, 5/2]
→ 같은 상태 안에서는 주문일 순서가 그대로 남는다
불안정 정렬이면 A와 C의 순서가 바뀔 수 있다. 숫자 배열처럼 같은 값을 구분할 필요가 없으면 안정성은 상관없다.
6. 비교 정렬의 하한과 비비교 정렬
두 원소를 비교하는 방식으로만 정렬하면, 가능한 순열 n!개를 구분해야 하므로 최소 log₂(n!) ≈ n log n번 비교가 필요하다. 이보다 빠르려면 비교하지 않는 정렬을 써야 한다.
| 알고리즘 | 방식 | 조건 |
| 계수 정렬 (Counting) | 값마다 개수를 세어 누적합으로 위치 계산 | 값의 범위 k가 작은 정수 |
| 기수 정렬 (Radix) | 자릿수별로 안정 정렬을 반복 | 자릿수가 정해진 정수·문자열 |
| 버킷 정렬 (Bucket) | 구간별 버킷에 나눠 담고 각각 정렬 | 값이 고르게 분포 |
7. 언어 내장 정렬
| API | 알고리즘 | 안정 |
| Java Arrays.sort(int[] 등 기본형) | Dual-Pivot Quicksort | X (기본형이라 구분 불필요) |
| Java Arrays.sort(Object[]), Collections.sort, List.sort | TimSort (병합 + 삽입 기반) | O |
| JavaScript Array.prototype.sort | 엔진 구현 (ES2019부터 명세상 안정 정렬 필수) | O |
자바스크립트 sort()는 비교 함수를 주지 않으면 문자열로 바꿔 비교한다. [10, 9, 1].sort()의 결과는 [1, 10, 9]다. 숫자는 sort((a, b) => a - b)로 정렬한다.
8. 실제로 어떻게 적용되나
- 정렬은 직접 구현하지 않는다: 실무에서는 내장 정렬에
Comparator만 정의한다.list.sort(Comparator.comparing(Order::getStatus).thenComparing(Order::getCreatedAt))처럼 여러 기준을 한 번에 지정하는 게 가장 명확하다. - DB에서 정렬할지 앱에서 정렬할지: 페이지 단위로 잘라야 하면 DB의
ORDER BY로 정렬해야 한다. 앱에서 정렬하면 이미 잘린 결과만 정렬하게 된다. - 상위 k개만 필요할 때: 전체를 정렬(O(n log n))하지 않고 크기 k짜리 힙(
PriorityQueue)을 유지하면 O(n log k)로 끝난다.
9. 면접 질문으로 정리
- Q. 퀵 정렬의 평균과 최악 복잡도, 최악이 생기는 경우는? 평균 O(n log n), 최악 O(n²)이다. 피벗이 매번 최솟값이나 최댓값으로 골라져 분할이 한쪽으로 치우칠 때(예: 정렬된 배열에서 첫 원소를 피벗으로) 생긴다.
- Q. 병합 정렬과 퀵 정렬을 비교하면? 병합 정렬은 항상 O(n log n)이고 안정하지만 O(n) 추가 메모리가 필요하다. 퀵 정렬은 제자리 정렬이고 평균적으로 더 빠르지만 최악 O(n²)이고 불안정하다.
- Q. 안정 정렬이란? 정렬 기준이 같은 원소들의 기존 상대 순서를 유지하는 정렬이다. 병합·삽입·버블 정렬이 안정, 퀵·힙·선택 정렬은 불안정하다.
- Q. 자바는 기본형과 객체 배열에 왜 다른 정렬을 쓰나? 기본형은 같은 값을 구분할 필요가 없어 빠른 퀵 정렬 계열을 쓰고, 객체는 안정성이 필요해 TimSort를 쓴다.
- Q. O(n log n)보다 빠른 정렬이 가능한가? 비교 기반으로는 불가능하다. 값의 범위가 제한된 정수라면 계수 정렬이나 기수 정렬로 선형 시간에 가능하다.