Algorithm #1. Sort algorithm. - 1.3 Bubble Sort algorithm.

이번은 거품정렬 . Bubble Sort에 대해서 알아보죠.

간단히 말해, 이런 이름이 붙은 이유는 정렬과정의 모양 때문입니다. 한 레코드와 인접한 index들을 비교해 가장 큰 레코드 값이
한 칸 한 칸씩 옆으로 밀려나가는 모습이 마치 거품모양과 같다 하여 이런 이름이 붙었다. .... 고 합니다. -_-;;;;;;;
- 전 그렇게 못 느끼겠습니다만. 제 상상력이 부족한 건가요????-

last index 가 n 인 문자열 배열 a 가 있다고 가정합시다.

이 문자열을 Alphabet order 로 Bubble Sort 를 써서 정렬하고자 한다면.

1. 레코드 값을 비교하기 위해 레코드 쌍을 마련한다. -> 이 경우, 인접한 요소끼리 레코드 쌍을 만든다.
   
   
2. 한 레코드 쌍의 첫번째와 두번째 요소를 비교한다. -> 만약 첫번째 레코드 값이 크다면, swap.
   
   
3. 다음 레코드 쌍을 마련한다. -> 다음 레코드 쌍의 첫 번째 요소는 직전 레코드 쌍의 두번째 요소.
   
   
4. 우선 n 개의 레코드 쌍을 검사하도록 하자.
   
   
5. 모든 레코드 쌍의 비교가 끝나면, 오름차순 정렬의 경우에 가장 큰 레코드 값이 배열의 마지막에
   대입되어 있을 것이다. -> a[n-1] 이 최대값.
   
   
6. n 이 1이 될 때 까지 위 알고리즘을 반복한다. -> 이 경우 마지막엔 단 1 개의 레코드 값만 남게 될 것이다.
   
   
7. 정렬 종료.

아주 간단합니다 -_-;
- 대체 이게 왜 거품인가요. -

직관적으로 느끼셨겠지만, Insertion Sort 와 거의 유사한 특성을 지닌다고 할수 있겠죠.

즉, 변수의 비교 횟수가 교환 횟수보다 압도적으로 적습니다.

단, 차이점이라면 Insertion Sort 는 서로 멀리 떨어진 값들을 교환하는 것에 반해, Bubble Sort 는 인접한 값을 교환합니다.

따라서, Insertion Sort 보다 정렬의 안정성이 높다고 할수 있겠죠.

이까지가 알고리즘 설명입니다.

그럼 코드로 구현해 보죠.

#include <stdio.h> int main() { int input[10]; int i, j; for(i=0 ; i<10 ; i++) { printf("[%d] 번째 수 입력 : ", i); scanf("%d",&input[i]); } /* 10개의 레코드를 정렬. */ for(i=10 ; i>=1 ; i--) { for(j=1 ; j < 10 ; j++) { /* 만약 한 레코드 쌍의 첫 번째 레코드가 두 번째 레코드보다 크다면 */ if(input[j-1] > input[j]) { /* swap */ input[j-1] ^= input[j]; input[j] ^= input[j-1]; input[j-1] ^= input[j]; } } } for(i=0 ; i<10 ; i++) { printf("%4d",input[i]); } printf("\n"); return 0; }

10개의 레코드를 정렬하는 예제입니다.

Insertion Sort 의 구현과 마찬가지로 C 언어를 이용했고, XOR 연산을 이용해 변수를  swap 했습니다.

자. 이걸 더 개선할 수 있을까요?

- 가능합니다.

Bubble Sort 는 레코드들의 교환 횟수가 매우 많습니다.

따라서, 일반적으로 알고리즘 시간 복잡도 상한은 O(N^2) 입니다.

하지만, O(N) 의 시간안에 Bubble Sort 가 수행될 수 있는 경우가 있습니다. 언제일까요?

 바로 이미 정렬된 배열의 경우입니다.

- 이 경우, Bubble 'Sort' 라는 말을 쓰기가 굉장히 민망하죠? -_-; -

아무튼. 이미 정렬된 배열의 경우엔 굳이 swap 할 이유가 없겠죠?

그럼 이 경우를 체크해서 이 코드를 조금 더 개선해 보도록 할까요.



#include <stdio.h> int main() { int input[10]; int i, j; int is_sorted; /* 이미 정렬된 배열인지 체크하는 변수. */ for(i=0 ; i<10 ; i++) { printf("[%d] 번째 수 입력 : ", i); scanf("%d",&input[i]); } /* 10개의 레코드를 정렬. */ for(i=10 ; i>=1 ; i--) { /* 우선 정렬된 배열이라 가정하자. */ is_sorted = 1; for(j=1 ; j < 10 ; j++) { /* 만약 한 레코드 쌍의 첫 번째 레코드가 두 번째 레코드보다 크다면 */ if(input[j-1] > input[j]) { /* swap */ input[j-1] ^= input[j]; input[j] ^= input[j-1]; input[j-1] ^= input[j]; /* 한 번이라도 swap이 일어난 경우는 정렬이 되어있지 않은 경우이므로 */ is_sorted = 0; } } /* is_sorted 가 1이라면 이미 정렬된 배열이므로 break 문을 통해 루프를 빠져나간다. */ if(is_sorted) { break; } } for(i=0 ; i<10 ; i++) { printf("%4d",input[i]); } printf("\n"); return 0; }


is_sorted 변수를 이용, 조건검사를 실행합니다.

따라서, 배열이 이미 정렬되어 있다면, 시간 복잡도의 상한은 O(N) 이 되겠죠.
- 당연히 내부 루프의 효율만을 따지게 될 테니까요. -



이것으로 Bubble Sort 알고리즘을 마치겠습니다. ㅇ_ㅇ