2. 정렬 (기초) - 버블, 선택, 삽입
2. 정렬 (기초) - 버블, 선택, 삽입
개념
정렬(Sorting)은 데이터를 특정 기준에 따라 순서대로 나열하는 알고리즘이다.
정렬의 분류
| 분류 | 설명 | 예시 |
|---|---|---|
| 비교 기반 | 원소 간 비교로 정렬 | 버블, 선택, 삽입, 퀵, 병합 |
| 비비교 기반 | 비교 없이 정렬 | 계수, 기수, 버킷 |
| 내부 정렬 | 메모리 내에서 정렬 | 대부분의 정렬 |
| 외부 정렬 | 외부 저장장치 활용 | 대용량 데이터 |
정렬의 특성
| 특성 | 설명 |
|---|---|
| 안정 정렬 (Stable) | 같은 값의 원소들의 상대적 순서가 유지됨 |
| 불안정 정렬 (Unstable) | 같은 값의 원소들의 순서가 바뀔 수 있음 |
| 제자리 정렬 (In-place) | 추가 메모리 O(1)만 사용 |
1
2
3
4
5
// 안정 정렬 예시
// 원본: (A, 3), (B, 1), (C, 3), (D, 2)
// 숫자 기준 정렬 후:
// 안정: (B, 1), (D, 2), (A, 3), (C, 3) ← A가 C보다 먼저 (원본 순서 유지)
// 불안정: (B, 1), (D, 2), (C, 3), (A, 3) ← 순서 바뀔 수 있음
버블 정렬 (Bubble Sort)
인접한 두 원소를 비교하여 교환하는 방식. 큰 원소가 거품처럼 뒤로 이동한다.
동작 원리
1
2
3
4
5
6
7
8
9
10
11
12
13
[5, 3, 8, 4, 2] - 초기
1회전: 가장 큰 원소 8이 맨 뒤로
[3, 5, 8, 4, 2] → [3, 5, 8, 4, 2] → [3, 5, 4, 8, 2] → [3, 5, 4, 2, 8]
2회전: 두 번째로 큰 5가 뒤에서 두 번째로
[3, 5, 4, 2, 8] → [3, 4, 5, 2, 8] → [3, 4, 2, 5, 8]
3회전:
[3, 4, 2, 5, 8] → [3, 2, 4, 5, 8]
4회전:
[2, 3, 4, 5, 8] - 완료
시간복잡도 & 특성
| 항목 | 값 |
|---|---|
| 최선 | O(N) - 이미 정렬된 경우 (최적화 시) |
| 평균 | O(N²) |
| 최악 | O(N²) |
| 공간 | O(1) |
| 안정성 | 안정 (Stable) |
| 제자리 | Yes |
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 기본 버전
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
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++) {
bool swapped = false;
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 = true;
}
}
if (!swapped) break; // 교환이 없으면 이미 정렬됨
}
}
선택 정렬 (Selection Sort)
매 회전마다 최솟값(또는 최댓값)을 찾아 맨 앞(또는 맨 뒤)과 교환하는 방식.
동작 원리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[5, 3, 8, 4, 2] - 초기
1회전: 최솟값 2를 찾아 첫 번째와 교환
[2, 3, 8, 4, 5]
↑ 확정
2회전: 나머지에서 최솟값 3을 찾아 두 번째와 교환
[2, 3, 8, 4, 5]
↑ 확정 (이미 제자리)
3회전: 나머지에서 최솟값 4를 찾아 세 번째와 교환
[2, 3, 4, 8, 5]
↑ 확정
4회전: 나머지에서 최솟값 5를 찾아 네 번째와 교환
[2, 3, 4, 5, 8] - 완료
시간복잡도 & 특성
| 항목 | 값 |
|---|---|
| 최선 | O(N²) |
| 평균 | O(N²) |
| 최악 | O(N²) |
| 공간 | O(1) |
| 안정성 | 불안정 (Unstable) |
| 제자리 | Yes |
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// 최솟값을 i번째와 교환
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
불안정 정렬인 이유
1
2
3
4
// 예시: [2a, 2b, 1] (2a와 2b는 같은 값)
// 1회전: 최솟값 1을 찾아 2a와 교환
// [1, 2b, 2a]
// 결과: 2a와 2b의 순서가 바뀜 → 불안정
삽입 정렬 (Insertion Sort)
각 원소를 이미 정렬된 부분의 적절한 위치에 삽입하는 방식. 카드 정렬과 유사.
동작 원리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[5, 3, 8, 4, 2] - 초기
1회전: 3을 정렬된 부분 [5]에 삽입
[3, 5, 8, 4, 2]
↑──↑ 정렬됨
2회전: 8을 정렬된 부분 [3, 5]에 삽입
[3, 5, 8, 4, 2]
↑─────↑ 정렬됨 (제자리)
3회전: 4를 정렬된 부분 [3, 5, 8]에 삽입
[3, 4, 5, 8, 2]
↑────────↑ 정렬됨
4회전: 2를 정렬된 부분 [3, 4, 5, 8]에 삽입
[2, 3, 4, 5, 8] - 완료
시간복잡도 & 특성
| 항목 | 값 |
|---|---|
| 최선 | O(N) - 이미 정렬된 경우 |
| 평균 | O(N²) |
| 최악 | O(N²) - 역순 정렬된 경우 |
| 공간 | O(1) |
| 안정성 | 안정 (Stable) |
| 제자리 | Yes |
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 기본 버전
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;
}
}
// swap 버전 (이해하기 쉬움)
void insertionSortSwap(int arr[], int n) {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
이진 삽입 정렬 (Binary Insertion Sort)
삽입 위치를 이진 탐색으로 찾아 비교 횟수를 줄임. 하지만 이동 횟수는 여전히 O(N²).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void binaryInsertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
// 이진 탐색으로 삽입 위치 찾기
int left = 0, right = i - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > key) right = mid - 1;
else left = mid + 1;
}
// left 위치에 삽입 (뒤로 이동)
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
}
비교 정리
시간/공간 복잡도
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정성 |
|---|---|---|---|---|---|
| 버블 | 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) | 불안정, 항상 O(N²) | 교환 비용이 클 때 |
| 삽입 | 거의 정렬된 데이터에 빠름 | 역순 데이터에 느림 | 소규모, 거의 정렬된 데이터 |
비교/교환 횟수
| 알고리즘 | 비교 횟수 | 교환(이동) 횟수 |
|---|---|---|
| 버블 | O(N²) | O(N²) |
| 선택 | O(N²) | O(N) |
| 삽입 | O(N²) | O(N²) |
면접 포인트
자주 나오는 질문
Q1. 버블, 선택, 삽입 정렬의 차이점은?
- 버블: 인접 원소 비교 및 교환, 안정
- 선택: 최솟값 찾아 교환, 교환 횟수 최소, 불안정
- 삽입: 적절한 위치에 삽입, 거의 정렬된 데이터에 효율적, 안정
Q2. 왜 선택 정렬은 불안정인가?
최솟값과 교환 시 같은 값의 상대적 순서가 바뀔 수 있음 예: [2a, 2b, 1] → [1, 2b, 2a]
Q3. 삽입 정렬이 거의 정렬된 데이터에 빠른 이유는?
이미 정렬된 부분에서 삽입 위치를 찾을 때 비교 횟수가 적음 최선의 경우 각 원소당 1번 비교 → O(N)
Q4. 실제로 이 정렬들을 언제 사용하나?
- 삽입 정렬: 소규모 데이터, 온라인 정렬, Tim Sort의 일부
- 선택 정렬: 메모리 쓰기 비용이 높을 때 (Flash Memory)
- 버블 정렬: 거의 사용 안 함 (교육 목적)
Q5. O(N²) 정렬이 O(N log N)보다 좋은 경우는?
- N이 작을 때 (N < 10~20): 상수 계수가 작은 삽입 정렬이 빠름
- 거의 정렬된 데이터: 삽입 정렬 O(N)
- Tim Sort는 작은 부분에서 삽입 정렬 사용
코드 구현 시 주의사항
1
2
3
4
5
6
7
8
9
// 1. 인덱스 범위 주의
for (int i = 0; i < n - 1; i++) // n-1까지
for (int j = 0; j < n - 1 - i; j++) // 버블: 이미 정렬된 부분 제외
// 2. 삽입 정렬: i는 1부터
for (int i = 1; i < n; i++) // 0번째는 이미 정렬됨
// 3. 선택 정렬: minIdx 갱신 조건
if (arr[j] < arr[minIdx]) // <, <= 아님 (안정성 관련)
STL 활용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <vector>
std::vector<int> v = {5, 3, 8, 4, 2};
// 기본 정렬 (오름차순)
std::sort(v.begin(), v.end());
// 내림차순
std::sort(v.begin(), v.end(), std::greater<int>());
// 안정 정렬 (stable_sort)
std::stable_sort(v.begin(), v.end());
// 부분 정렬 (상위 k개만)
std::partial_sort(v.begin(), v.begin() + k, v.end());
// 커스텀 비교 함수
std::sort(v.begin(), v.end(), [](int a, int b) {
return a > b; // 내림차순
});
추천 문제
This post is licensed under CC BY 4.0 by the author.