| 정렬 | 평균 | 최악 | 최선 | 공간 | 안정성 | 특징 |
|---|---|---|---|---|---|---|
| 버블 | O(N²) | O(N²) | O(N) | O(1) | ✔ | 인접 원소 교환 |
| 선택 | O(N²) | O(N²) | O(N²) | O(1) | ✘ | 최솟값 선택 |
| 삽입 | O(N²) | O(N²) | O(N) | O(1) | ✔ | 적절한 위치 삽입 |
| 퀵 | O(N log N) | O(N²) | O(N log N) | O(log N) | ✘ | 피벗 기준 분할 |
안정성(Stable): 같은 값의 순서가 정렬 후에도 유지되는가?
인접한 두 원소를 비교하여 큰 값을 뒤로 보내는 정렬
배열: [5, 3, 8, 1, 2]
1회전: 가장 큰 값(8)을 맨 뒤로
[5, 3, 8, 1, 2]
└─┘ 비교 → [3, 5, 8, 1, 2]
└─┘ 비교 → [3, 5, 8, 1, 2]
└─┘ 비교 → [3, 5, 1, 8, 2]
└─┘ 비교 → [3, 5, 1, 2, 8] ✔
2회전: 두 번째로 큰 값(5)을 뒤에서 두 번째로
[3, 5, 1, 2, 8]
└─┘ 비교 → [3, 5, 1, 2, 8]
└─┘ 비교 → [3, 1, 5, 2, 8]
└─┘ 비교 → [3, 1, 2, 5, 8] ✔
3회전: [3, 1, 2, 5, 8]
└─┘ 비교 → [1, 3, 2, 5, 8]
└─┘ 비교 → [1, 2, 3, 5, 8] ✔
4회전: [1, 2, 3, 5, 8] ✔ 정렬 완료
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { // n-1회전
for (int j = 0; j < n - 1 - i; j++) { // 비교 횟수 감소
if (arr[j] > arr[j + 1]) {
// 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void bubbleSortOptimized(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; // 교환 발생 여부
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
// 교환이 없으면 이미 정렬됨
if (swapped == 0) break;
}
}
비교 횟수:
1회전: n-1번
2회전: n-2번
3회전: n-3번
...
n-1회전: 1번
총: (n-1) + (n-2) + ... + 1 = n(n-1)/2
최선: O(N) - 이미 정렬된 경우 (최적화 버전)
평균: O(N²)
최악: O(N²) - 역순 정렬된 경우
공간복잡도: O(1) - 추가 메모리 불필요
장점:
✔ 구현이 매우 간단
✔ 안정 정렬 (Stable)
✔ 추가 메모리 불필요
단점:
✘ 느린 속도 O(N²)
✘ 데이터가 많으면 비효율적
✘ 실무에서 거의 사용 안 함
전체에서 최솟값을 찾아 맨 앞과 교환하는 정렬
배열: [5, 3, 8, 1, 2]
1회전: 최솟값(1) 찾아서 맨 앞과 교환
[5, 3, 8, 1, 2]
↓찾기→ ↑최솟값
[1, 3, 8, 5, 2] ✔ 1 고정
2회전: 나머지에서 최솟값(2) 찾아서 두 번째와 교환
[1, 3, 8, 5, 2]
↓찾기→ ↑최솟값
[1, 2, 8, 5, 3] ✔ 2 고정
3회전: 나머지에서 최솟값(3) 찾아서 세 번째와 교환
[1, 2, 8, 5, 3]
↓ ↑최솟값
[1, 2, 3, 5, 8] ✔ 3 고정
4회전: [1, 2, 3, 5, 8]
↓ ↑최솟값
[1, 2, 3, 5, 8] ✔ 5 고정
최종: [1, 2, 3, 5, 8] ✔
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 최솟값의 인덱스 찾기
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 최솟값과 현재 위치 교환
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
비교 횟수:
1회전: n-1번
2회전: n-2번
...
n-1회전: 1번
총: n(n-1)/2
최선: O(N²) - 이미 정렬되어도 모든 비교 수행
평균: O(N²)
최악: O(N²)
교환 횟수: 최대 N-1번 (버블보다 적음)
공간복잡도: O(1)
장점:
✔ 구현이 간단
✔ 교환 횟수가 적음 (최대 n-1번)
✔ 추가 메모리 불필요
단점:
✘ 느린 속도 O(N²)
✘ 불안정 정렬 (Unstable)
✘ 이미 정렬되어도 모든 비교 수행
배열: [3₁, 3₂, 1]
1회전: 최솟값 1을 찾아 3₁과 교환
[1, 3₂, 3₁]
3₁과 3₂의 순서가 바뀜 → 불안정 ✘
정렬된 부분에 새 원소를 적절한 위치에 삽입하는 정렬
배열: [5, 3, 8, 1, 2]
초기: [5] | 3, 8, 1, 2
정렬됨 | 미정렬
1회전: 3을 정렬된 부분에 삽입
[5] | 3, 8, 1, 2
↓ 3 < 5 → 앞으로 이동
[3, 5] | 8, 1, 2 ✔
2회전: 8을 정렬된 부분에 삽입
[3, 5] | 8, 1, 2
↓ 8 > 5 → 그대로
[3, 5, 8] | 1, 2 ✔
3회전: 1을 정렬된 부분에 삽입
[3, 5, 8] | 1, 2
↓ 1 < 3 → 맨 앞으로
[1, 3, 5, 8] | 2 ✔
4회전: 2를 정렬된 부분에 삽입
[1, 3, 5, 8] | 2
↓ 2 > 1, 2 < 3
[1, 2, 3, 5, 8] ✔
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // 삽입할 값
int j = i - 1;
// key보다 큰 원소들을 뒤로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // 적절한 위치에 삽입
}
}
arr[] = {5, 3, 8, 1, 2}
i=1, key=3:
j=0: arr[0]=5 > 3 → arr[1]=5
j=-1: 종료
arr[0]=3
결과: [3, 5, 8, 1, 2]
i=2, key=8:
j=1: arr[1]=5 < 8 → 종료
arr[2]=8
결과: [3, 5, 8, 1, 2]
i=3, key=1:
j=2: arr[2]=8 > 1 → arr[3]=8
j=1: arr[1]=5 > 1 → arr[2]=5
j=0: arr[0]=3 > 1 → arr[1]=3
j=-1: 종료
arr[0]=1
결과: [1, 3, 5, 8, 2]
i=4, key=2:
j=3: arr[3]=8 > 2 → arr[4]=8
j=2: arr[2]=5 > 2 → arr[3]=5
j=1: arr[1]=3 > 2 → arr[2]=3
j=0: arr[0]=1 < 2 → 종료
arr[1]=2
결과: [1, 2, 3, 5, 8] ✔
최선: O(N) - 이미 정렬된 경우
각 원소마다 1번만 비교
평균: O(N²) - 무작위 배열
최악: O(N²) - 역순 정렬
1+2+3+...+(n-1) = n(n-1)/2
공간복잡도: O(1)
장점:
✔ 간단한 구현
✔ 안정 정렬 (Stable)
✔ 이미 정렬된 경우 O(N)으로 매우 빠름
✔ 작은 데이터셋에 효율적
✔ 온라인 알고리즘 (데이터 추가 시 바로 정렬 가능)
단점:
✘ 평균적으로 O(N²)
✘ 대량 데이터에 비효율적
✔ 거의 정렬된 배열
✔ 데이터가 적을 때 (n < 50)
✔ 온라인 정렬 (실시간 데이터 추가)
✔ 다른 고급 정렬의 기본 단계 (TimSort 등)
피벗(Pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하는 정렬
배열: [5, 3, 8, 1, 2, 9, 4]
1단계: 피벗 선택 (마지막 원소 4)
[5, 3, 8, 1, 2, 9, 4]
↑피벗
2단계: 분할 (Partition)
- 4보다 작은 값 → 왼쪽
- 4보다 큰 값 → 오른쪽
[3, 1, 2] 4 [5, 8, 9]
←작음 피벗 큼→
3단계: 왼쪽 부분 재귀 정렬
[3, 1, 2] → 피벗 2
[1] 2 [3]
4단계: 오른쪽 부분 재귀 정렬
[5, 8, 9] → 피벗 9
[5, 8] 9 []
[5] 8 []
최종: [1, 2, 3, 4, 5, 8, 9] ✔
// 분할 함수
int partition(int arr[], int left, int right) {
int pivot = arr[right]; // 마지막 원소를 피벗으로
int i = left - 1; // 작은 원소의 마지막 인덱스
for (int j = left; j < right; j++) {
// 피벗보다 작으면 왼쪽으로
if (arr[j] < pivot) {
i++;
// 교환
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 피벗을 중간으로 이동
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1; // 피벗의 최종 위치
}
// 퀵 정렬 함수
void quickSort(int arr[], int left, int right) {
if (left < right) {
// 분할
int pivotIndex = partition(arr, left, right);
// 왼쪽 부분 정렬
quickSort(arr, left, pivotIndex - 1);
// 오른쪽 부분 정렬
quickSort(arr, pivotIndex + 1, right);
}
}
// 호출 방법
int main() {
int arr[] = {5, 3, 8, 1, 2, 9, 4};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
return 0;
}
arr[] = {5, 3, 8, 1, 2, 9, 4}
pivot = 4, i = -1
j=0: arr[0]=5 ≥ 4 → pass
j=1: arr[1]=3 < 4 → i=0, swap(arr[0], arr[1])
[3, 5, 8, 1, 2, 9, 4]
j=2: arr[2]=8 ≥ 4 → pass
j=3: arr[3]=1 < 4 → i=1, swap(arr[1], arr[3])
[3, 1, 8, 5, 2, 9, 4]
j=4: arr[4]=2 < 4 → i=2, swap(arr[2], arr[4])
[3, 1, 2, 5, 8, 9, 4]
j=5: arr[5]=9 ≥ 4 → pass
피벗 이동: swap(arr[3], arr[6])
[3, 1, 2, 4, 8, 9, 5]
↑
피벗 위치
분할 완료:
[3, 1, 2] | 4 | [8, 9, 5]
왼쪽 피벗 오른쪽
최선/평균: O(N log N)
- 균등 분할되는 경우
- 트리 높이: log N
- 각 레벨: N번 비교
최악: O(N²)
- 이미 정렬된 배열 + 끝을 피벗으로
- 한쪽으로만 분할
- 높이: N
공간복잡도: O(log N)
- 재귀 호출 스택
최선 (균등 분할):
[5,3,8,1,2,9,4]
/ \
[3,1,2] [8,9,5]
/ \ / \
[1] [3] [5] [9]
높이: log N
각 레벨: N번 비교
시간: O(N log N) ✔
최악 (편향 분할):
[1,2,3,4,5]
\
[2,3,4,5]
\
[3,4,5]
\
[4,5]
\
[5]
높이: N
시간: O(N²) ✘
1. 마지막 원소 (구현 간단)
✘ 정렬된 배열에서 최악
2. 첫 원소
✘ 정렬된 배열에서 최악
3. 중간 원소
✔ 약간 개선
4. 무작위 선택
✔ 평균적으로 O(N log N)
5. Median-of-Three (추천) ✔
- 첫, 중간, 끝 중 중앙값
- 최악의 경우 방지
int medianOfThree(int arr[], int left, int right) {
int mid = (left + right) / 2;
// 세 값 정렬
if (arr[left] > arr[mid]) {
swap(&arr[left], &arr[mid]);
}
if (arr[left] > arr[right]) {
swap(&arr[left], &arr[right]);
}
if (arr[mid] > arr[right]) {
swap(&arr[mid], &arr[right]);
}
// 중앙값을 right-1로 이동
swap(&arr[mid], &arr[right - 1]);
return arr[right - 1]; // 피벗 반환
}
장점:
✔ 평균 O(N log N)으로 빠름
✔ 추가 메모리 적음 O(log N)
✔ 실무에서 가장 많이 사용
✔ 캐시 효율적 (in-place)
단점:
✘ 최악의 경우 O(N²)
✘ 불안정 정렬 (Unstable)
✘ 재귀 호출 오버헤드
✔ 대부분의 범용 정렬
✔ C 표준 라이브러리 qsort()
✔ 평균 성능이 중요한 경우
✔ 메모리가 제한적일 때
n < 10:
→ 삽입 정렬 (간단, 빠름)
10 ≤ n < 50:
→ 삽입 정렬 또는 선택 정렬
n ≥ 50:
→ 퀵 정렬 (Median-of-Three)
→ 또는 병합 정렬 (안정 정렬 필요 시)
이미 정렬된 데이터:
→ 삽입 정렬 O(N) ✔
거의 정렬된 데이터:
→ 삽입 정렬 ✔
완전 무작위:
→ 퀵 정렬 ✔
안정 정렬 필요:
→ 버블, 삽입 (작은 데이터)
→ 병합 정렬 (큰 데이터)
메모리 제한:
→ 퀵 정렬 (in-place) ✔
최악 보장:
→ 병합 정렬 또는 힙 정렬