Optimized Bubble Sort (최적화된 버블 정렬)

알고리즘 

사실 최적화라고 하기 민망할 정도로 버블정렬과 큰 차이가 없으며 

실제 코드상으로도 단 2글자만 추가되었을 뿐이다.

최적화된 버블 정렬의 주된 아이디어는, 

맨 마지막 원소는 이미 정렬 되어있어서 또 검사해줄 필요가 없다는 것이다.

즉, 버블 정렬의 첫번째 패스를 눈여겨 살펴보면,

가장 큰 값이 항상 맨 끝으로 이동된다.

어찌보면 당연한 결과라고 할 수 있다. 

가장 큰 값은 if문에 발각되어 계속 Swap 되기 때문에, 맨 뒤까지 질질 끌려간다.

결론적으로, 두번째 패스에서는 마지막 원소를 검사해줄 필요가 없다.

세번째 패스에서는 마지막 원소와 마지막에서 두번째 원소 역시 검사해줄 필요가 없다.

마지막 패스에서는 두번째 원소와 첫번째 원소만 검사해주면 된다.

코드

#include <stdio.h>

void op_bubble_sort(int num[],int len);
void tracer(int num[],int len);

int main(void){
    int testArr[] = {485,241,454,325,452,685,498,890,281};
    int len = sizeof(testArr)/sizeof(int);
    op_bubble_sort(testArr,len);
}

void op_bubble_sort(int num[],int len){
    int i,j,tempINT;
    for(i=0; i<len-1; i++){
        for(j=0; j<len-i-1; j++){  
        // len-1 대신 len-i-1 으로 바뀌었다.
        // i가 커지면, 배열의 뒷 부분은 검사하지 않을 것이다.
            if(num[j+1] < num[j]){
                tempINT = num[j];
                num[j] = num[j+1];
                num[j+1] = tempINT;
            }
        }
        tracer(num,len);
    }
}

void tracer(int num[],int len){
    int i;
    for(i=0;i<len;i++){
        printf("%d\t",num[i]);
    }
    printf("\n");
}

결과

표면적으로는 차이가 없다. 다만 연산 횟수가 조금 줄어들었을 뿐이다.