버블정렬(Bubble Sort) - 교환정렬

버블 정렬은 나란히 있는 두개의 데이터를 비교하여 순서를 바꾸는 정렬방법입니다.

다음과 같은 데이터가 있다고 가정한 후

A B C D E F

A값이 맨 뒤로 가게 버블 정렬을 한다면 정렬의 진행은 다음과 같습니다.

1.B C D E FA

2.C D E F B A

3. D E FC B A

4. E FD C B A

5. F E D C B A

즉, N개의 데이터가 있다면 연결되어 있는 데이터를 비교하여 순서를 계속 바꾸는 방법으로 정렬하는 방법을 사용합니다. 알고리즘으로서는 좋은 알고리즘은 아닙니다. 비교 검색 시간은 N-1, N-2, N-3 ... 이러식으로 순차적으로 비교하면 교환 수는 정렬되어 있는 상태에 따라 다르지만 정렬상태가 난수적으로 되어 있다면 교환 수도 증가합니다.

버블 정렬 알고리즘

void bubble_sort(int a[], int n) // 버블 정렬함수
{
    int i, j, t;

    for(i=0; i<n-1; i++) {
        for(j=1; j<n-i; j++) {
            if(a[j-1]>a[j]) {
                t=a[j-1];
                a[j-1]=a[j];
                a[j]=t;
            }
        }
    }
}

버블 정렬을 개선한 알고리즘

버블 정렬을 개선한 알고리즘은 내부 비교시에 교환이 일어나지 않았다면 더 이상의 비교,교환의 진행이 필요없음을 나타내기 때문에 데이터 교환시에는 계속 수행을 시키고 데이터 교환이 일어나지 않았다면 반복문을 종료하는 방법을 추가시키는 것입니다.

void bubble_sort(int a[], int n) // 버블 정렬함수
{
    int i, j, t;

     int flag = 1;

    for( i = n-1; flag > 0; i++) {

          flag = 0;

        for(j=1; j<i; j++) {
            if(a[j-1]>a[j]) {    // if문이 수행되지 않으면 반복문을 종료
                t=a[j-1];
                a[j-1]=a[j];

                a[j]=t;

                flag = 1;

            }
        }
    }
}