버블정렬(거품정렬 : Bubble sort) - C++로 버블정렬 하는 방법을 알아보자.

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다.
시간 복합도가 O(n2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다.
원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
- 출처 : 위키백과

수열 "10 9 4 8 5 1 7" 을 버블 정렬을 이용하여 오름차순으로 정렬하는 방법은 다음과 같다.
결과)

소스)

#define SWAP(x, y) {int t=x; x=y; y=t;}

int main()
{
    int a[7]={10, 9, 4, 8, 5, 1, 7};
    int i, j;

    for (i=1; i<7; i++){
        for (j=0; j<7-i; j++){
            if (a[j] > a[j+1])SWAP(a[j], a[j+1]);
        }
    }

    for (i=0; i<7; i++){
        printf ("%d ", a[i]);
    }

    return 0;
}

다음 수열 "10 9 4 5 6 7 8" 은 두번만에 정렬이 끝나게 된다. 이런경우 나머지 5번의 작업은 의미가 없다.
정렬작업 중 정렬이 다 되었으면 작업을 마치는 방법은 다음과 같다.
결과) 

 소스)

#define SWAP(x, y) {int t=x; x=y; y=t;}

int main()
{
    int a[7]={10, 9, 4, 5, 6, 7, 8};
    int i, j, flag;

    for (i=1; i<7; i++){
        flag=0;
        for (j=0; j<7-i; j++){
            if (a[j] > a[j+1]){
                SWAP(a[j], a[j+1]);
                flag=1;
            }
        }
        if (flag==0) break;
    }

    for (i=0; i<7; i++){
        printf ("%d ", a[i]);
    }

    return 0;
}