1. 버블 정렬 (Bubble Sort) 이란?
: 인접한 두 원소를 검사하여 정렬하는 방법
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보임
코드가 단순해 자주 사용되는 정렬 알고리즘
↑
무작위 배열수의 버블 정렬 예
2. 장단점
- 장점 : 코드가 단순하다
- 단점 : 느리다 ( T(n) = O(n2) )
3. 버블 정렬 실행 과정 (오름차순)
정렬할 배열
4 |
1 |
5 |
2 |
3 |
4 > 1 이므로 자리교체
4 | 1 | 5 | 2 | 3 |
1 | 4 | 5 | 2 | 3 |
4 < 5 이므로 자리교체 X
1 | 4 | 5 | 2 | 3 |
5 > 2 이므로 자리교체
1 | 4 | 5 | 2 | 3 |
1 | 4 | 2 | 5 | 3 |
5 > 3 이므로 자리교체 (가장 큰 수 5 고정됨)
1 | 4 | 2 | 5 | 3 |
1 | 4 | 2 | 3 | 5 |
1 < 4 이므로 자리교체 X
1 | 4 | 2 | 3 | 5 |
4 > 2 이므로 자리교체
1 | 4 | 2 | 3 | 5 |
1 | 2 | 4 | 3 | 5 |
4 > 3 이므로 자리교체 (두 번째로 큰 수 4 고정됨)
1 | 2 | 4 | 3 | 5 |
1 | 2 | 3 | 4 | 5 |
1 < 2 이므로 자리교체 X
1 | 2 | 3 | 4 | 5 |
2 < 3 이므로 자리교체 X (세 번째로 큰 수 3 고정됨)
1 | 2 | 3 | 4 | 5 |
1 < 2 이므로 자리교체 X (네 번째로 큰 수, 가장 작은 수 2, 1 고정됨)
1 | 2 | 3 | 4 | 5 |
4. C 언어 소스 코드 (오름차순)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <stdio.h>
int main() { int arr[] = {3, 1, 2, 5, 4}; int size = sizeof(arr) / sizeof(int); int temp; for (int i = 0; i < size - 1; i++) { for (int j = 0; j < size - 1 - i; j++) { if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } } |
5. 성능 분석
- 시간 복잡도
: T(n) = O(n2)
- 공간 복잡도
: 제자리 정렬 (In-place sort)
원소를 담는 공간 외에 옮겨지는 원소가 저장되는 공간 (위 소스 코드에서의 temp), 루프 변수 (위 소스 코드에서의 i, j) 만이 추가로 사용됨
※ 제자리 정렬 (In-place sort) 이란?
: 원소들의 갯수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘
'알고리즘' 카테고리의 다른 글
| 알고리즘 성능 분석 (0) | 2017.05.28 |
|---|---|
| 컴퓨터 알고리즘이란? (0) | 2017.05.26 |