[C/C++]정렬 - 버블정렬 bubble sort

자료구조

버블정렬의 핵심은 인접한 2개의 원소가 비교,교환된다는 것입니다.

 

한번의 동작만에 정렬되는 경우가 매우 드물고 전체 숫자가 모두 정렬될 때 까지 진행됩니다.

 

전체 배열 값 중에 제일 큰 값이 오른쪽에 쌓이기 시작하고 그게 반복되다보면 정렬이 완성됩니다.

 

#define SWAP(x,y,t) ((t=x),(x=y),(y=t))

void bubble(int list[], int size){
    int i,j,tmp;
    for(i = size-1; i>0; i--){
        for(j=0;j<i;j++){
            if(list[j]>list[j+1]) SWAP(list[j],list[j+1],tmp);
        }
    }
}

오른쪽 끝부터 채울 것이기 때문에 외부 for문은 큰 숫자 먼저, 내부 for문은 하던대로 합니다.

 

이전 원소가 다음 원소보다 크다면 위치를 바꿔주는 게 내부 for문의 역할입니다.

 

▣복잡도 분석

 

버블정렬은 모든 원소를 비교하기 때문에 비교횟수만 고려할 때 최선,평균,최악의 경우가 따로 없습니다.

 

for문 2개 중첩에 비교연산 하나 들어가 있으니 n(n-1)/2가 되겠습니다.

 

이동 횟수의 경우 SWAP 매크로함수가 3이기 때문에 역정렬된 경우(이동연산을 고려하면 최악의 경우) 3 * n(n-1)/2가 됩니다.

 

O(n²)가 결론으로 나옵니다.

 

버블정렬은 매우 낭비가 심한 정렬인데 그 이유는 비교연산이 압도적으로 많기 때문입니다. 한 원소가 끝 위치 까지 가기 위한 비교연산+이동연산은 모든 원소와 수행되므로 낭비가 심한 것을 알 수 있죠.

 

 

"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"