오늘은 가장 단순, 무식한 알고리즘인 거품 정렬에 대해 알아 보도록 하겠습니다.
▶ 선택 정렬 (Selection Sort)
▶ 삽입 정렬 (Insert Sort)
▶ 삽입 정렬 (Insert Sort)
▶ 거품 정렬 (Bubble Sort)
▶ 퀵 정렬 (Quick Sort)
▶ 힙 정렬 (Heap Sort)
3. 거품 정렬
거품 정렬은 알고리즘을 통한 정렬 과정이 거품이 보글보글 올라오는 것과 같다고 해서 거품 정렬이라는 이름이 붙여졌습니다.
정렬 알고리즘 중 가장 단순하고, 느리다고 알려져 있는데 그럼 정말 그런지 살펴 볼까요?
| ↓ 배열 포인터 (array[0]) | 3 | 4 | 2 | 1 | 1. i = 0 이며, i 가 n-1이 되면 종료된다. 2. 현재 배열 포인터와 다음 포인터의 값을 비교하여 array[j] > array]j + 1] 라면 두 값을 교환한다. i = 0, j = 0; ↓ 배열 포인터 (array[j]) | 3 | 4 | 2 | 1 | i = 0, j = 1; ↓ 배열 포인터 (array[j]) | 3 | 2 | 4 | 1 | i = 0, j = 2; ↓ 배열 포인터 (array[j]) | 3 | 2 | 4 | 1 | i = 0, j = 3; ↓ 배열 포인터 (array[j]) | 3 | 2 | 1 | 4 | 3. j 가 n - i 이면, j = 0 으로 하고, i 를 1만큼 증가시킨다. i = 1, j = 0; ↓ 배열 포인터 (array[j]) | 2 | 3 | 1 | 4 | i = 1, j = 1; ↓ 배열 포인터 (array[j]) | 2 | 3 | 1 | 4 | i = 1, j = 2; ↓ 배열 포인터 (array[j]) | 2 | 1 | 3 | 4 | 4. 3 단계를 반복한다. i = 2, j = 0; ↓ 배열 포인터 (array[j]) | 2 | 1 | 3 | 4 | i = 2, j = 1; ↓ 배열 포인터 (array[j]) | 1 | 2 | 3 | 4 | 5. i 가 n - 1 이면 정렬을 종료한다. |
정말 거품이 보글보글 올라가는 모습이 보이시나요?
자세히 보면 끝에서 부터 차례로 정렬이 되는 모습을 확인 하실 수 있습니다. 그래서 거품이 조금씩 작아지는 것이죠.
n 개의 데이터를 정렬하기 위해서는 n + (n - 1) + (n - 2)..... 번의 비교 과정과 일련의 교환 과정이 수행되어야 합니다.
교환 과정을 제외한 비교는 n(n - 1)/2 번을 수행하게 됩니다. 따라서 복잡도는 O(n2) 입니다.
따라서 실행시간은 느리다는 것을 알 수 있습니다.
그럼 코드를 살펴보도록 하겠습니다.
| #include <stdio.h>
#define SWAP(a, b) { int t = a; a = b; b = t; }
{ int i=0, j; for (; i < n - 1; i++) { for (j=0; j < n - (i + 1); j++) { if (array[j] > array[j+1]) { SWAP(array[j], array[j+1]); } // if } // for } // for } int main(void) { char array[LEN]={3, 4, 2, 1}; char i=0;
printf(" %d", array[i]);
printf(" %d", array[i]);
} |
별도의 추가적인 코멘트는 달지 않도록 하겠습니다.
'컴퓨터 > 프로그래밍' 카테고리의 다른 글
| [알고리즘] 정렬(sort) - 거품 정렬 (0) | 2010/12/13 |
|---|---|
| [알고리즘] 정렬(sort) - 삽입 정렬 (0) | 2010/12/03 |
| [알고리즘] 정렬(sort) - 선택 정렬 (0) | 2010/12/01 |
| [알고리즘] 유클리드 알고리즘 (0) | 2010/11/23 |
