. 버블정렬이란? -. 인접해 있는 두 개의 값을 비교해서 자료 교환을 한다. -. 오름차순 정렬은 두 개의 값을 비교해서 큰 값을 오른쪽으로 보내는 방식이다, 내림차순 정렬은 두 개의 값을 비교해서 작은 값을 오른쪽으로 보내는 방식이다. 2. 버블정렬(Bubble Sort)과 유사한 용어 -. Interchange Sort -. Shifting Sort 3. 버블정렬을 이용하여 오름차순으로 정렬하는 방법 4. 버블정렬의 비교회수 -. 비교 회수 공식 : N(N – 1)/2 -. 위의 그림을 보시면 아시겠지만 제일 처음에는 (N – 1)번을 비교하고, 그 다음에는 (N – 2)번 만큼 비교하고, 그 다음은 (N – 3)번을 비교하면서 비교회수가 1이 될 때까지 이 작업을 반복할 것이다. -. 비교회수는 (N – 1) + (N – 2) + (N – 3) …… + 1 이 될 것이다. 최대 (N – 1)번을 수행할 것이며, 각 패스가 수행할 때마다 수학식으로 표현하면 -. 5개의 값을 오름차순으로 버블정렬을 하면... 공식에 의해서 5(5 – 1)/2 = 10 가 성립된다. 즉, 총 10번의 비교를 통해서 오름차순으로 정렬된 값을 볼 수 있다. 5. 버블정렬의 연산시간 -. 연산시간 공식 : O(n²) -. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’ (Worst Case)에 대한 연산시간을 나타낸다. 6. 버블정렬의 장점 -. 인접해 있는 두 개의 값을 비교하여 자료의 위치를 이동시키므로 단순하다. -. 여러 차례 값을 비교하므로 안전성 있게 값을 정렬한다. 7. 버블정렬의 단점 -. 첫번째 패스에서 자료의 교환이 없었다면 주어진 값은 이미 오름차순으로 정렬된 상태이지만, 최대 N(N – 1)/2 만큼의 비교회수와 O(n²) 만큼의 연산시간이 소요된다. -. 다른 정렬에 비해서 연산시간이 오래 걸린다. 8. 버블정렬을 이용해서 작성한 예제 #include "stdio.h" void Bubble_Sort(int parm_data[], int parm_count) { int i, j, temp = 0; int comparison_count = 0; for(i = 0; i < parm_count - 1; i++){ for(j = 0; j < parm_count - 1 - i; j++){ comparison_count++; if(parm_data[j] > parm_data[j+1]){ temp = parm_data[j]; parm_data[j] = parm_data[j+1]; parm_data[j+1] = temp; } } } printf("총 비교회수는 [ %d 회] 이다.", comparison_count); printf("\n\n\n"); } void main() { int array[5] = {7, 4, 11, 9, 2}; int i; printf("=== 버블정렬하기 전 ===\n\n"); for(i = 0; i < 5; i++) printf("%d ", array[i]); printf("\n\n"); printf("================================"); printf("\n\n"); Bubble_Sort(array, 5); printf("=== 버블정렬한 후 ===\n\n"); for(i = 0; i < 5; i++) printf("%d ", array[i]); printf("\n\n"); }
이므로 공식은 N(N – 1)/2 이런 공식이 성립된다.
결과는 아래와 같습니다.
'정보처리기사 > 데이터베이스' 카테고리의 다른 글
| 선택 정렬(Selection Sort) 알고리즘 (0) | 2013.05.01 |
|---|---|
| 트리 순회 방법 (0) | 2013.05.01 |