버블 소트는 인접원소를 비교해서 더 큰 원소를 뒤로 보내는 방식을 사용한다. 병 밑바닥에서 생긴 버블이 위로 올라오면서 점점 더 커지는 것과 비슷하기 때문에 버블소트라고 명명하게 되었다.
매우 간단하게 구현할 수 있지만, 많은 경우에 있어서 매우 비효율적이라는 단점을 가진다.
예를들어 퀵소트(:12)는 평균 시간복잡도가 O(nlogn) 인데 비해서 버블소트는 항상 O(n^2) 이라는 최악의 시간복잡도를 보여주기 때문이다. - 물론 몇 가지 수정사항을 포함시키면 복잡도를 줄일 수 있지만 예외로 한다 -
정렬해야할 데이터의 갯수가 매우 적은 경우가 아니라면 퀵소트(:12)가 사용하기에 가장 무난한 성능을 보여준다. 여러가지 상황에 따른 소트 알고리즘(:12)의 선택에 대해서는 따로 문서를 작성해 보도록 하겠다.
다음은 퀵소트가 이루어지는 과정을 Visual 하게 보여주고 있다.
다음은 C(:12)언어로 구현된 퀵소트 알고리즘이다.
#include <stdio.h>
void b_sort(int data[], int size)
{
int tmp = 0;
int i, j;
int comparison = 0;
int swap = 0;
for (i = 0; i < size-1; i++)
{
for (j = 0; j < (size-1); j++)
{
comparison++;
if (data[j] > data[j+1])
{
tmp = data[j+1];
data[j+1] = data[j];
data[j] = tmp;
swap++;
}
}
}
printf("Comparisons %d\n", comparison);
printf("Swap %d\n", swap);
}
위의 코드는 버블소트 알고리즘을 그대로 표현해주고 있으며 O(n^2)의 시간복잡도를 보여준다. 이 방식으로 하자면 완전히 정렬된 데이터의 정렬에 대해서도 O(n^2)의 시간복잡도를 보여준다. 단지 Swap과정만이 생략될 뿐이다.
여기에 약간의 조건을 주면 시간복잡도를 줄일 수 있으며, 완전히 정렬된 데이터에 대해서는 O(n)의 시간복잡도를 가지도록 개선할 수도 있다. 힌트를 주자면 swap이 일어났는지를 검사하는 flag를 둬서, swap이 일어나지 않았다면 정렬이 끝난것으로 판단하는 것이다. 이 방법은 직접 테스트해보기 바란다.
#include <stdio.h> void b_sort(int data[], int size) { int tmp = 0; int i, j; int comparison = 0; int swap = 0; for (i = 0; i < size-1; i++) { for (j = 0; j < (size-1); j++) { comparison++; if (data[j] > data[j+1]) { tmp = data[j+1]; data[j+1] = data[j]; data[j] = tmp; swap++; } } } printf("Comparisons %d\n", comparison); printf("Swap %d\n", swap); }Recent Posts
Archive Posts
Tags