C언어 : 기존 버블정렬과 개선된 버블 정렬 (bubble sort)

버블 정렬이란?

버블 정렬(bubble sort)은 인접한 원소와 비교하여 순서가 바뀌었으면 서로 교환하여 정렬하는 방법이다.

첫 번째 원소부터 비교를 시작하면 가장 큰 값이 마지막에 위치하게 되고,

그 다음에 나머지 n-1개의 원소에 대해서 이 과정을 실시하면 두번째로 큰 원소가 n-1번째에 위치하게 된다.

 

기존의 버블 정렬 코드는 아래와 같다.

void bubble_sort(int data[], int n) {
    int temp;
    int max;
 
    for (int i = n-1; i >= 1; i--) {
        for (int j = 0; j < i; j++) {
            if (data[j] > data[j + 1]) {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }    
}

 

개선된 버블 정렬이란?

버블 정렬에서 각 단계에서 자료의 교환이 더이상 발생하지 않으면 정렬이 끝난 것을 의미하므로 다음 단계를 실행하지 않고 정렬을 종료할 수 있다. 이렇게 하면 정렬 실행 시간이 단축된다.

void advanced_bubble_sort(int data[], int n) {
    int i, j;
    int temp;
    int flag = 1;    //1이면 자료 교환이 발생했음을 나타냄
 
    for (i = n - 1; flag&&i >= 1; i--) {
        flag = 0;
        for(j=0; j<i; j++)
            if (data[j] > data[j + 1]) {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
                flag = 1;
            }
    }
}