Bubble Sort (버블 정렬)

알고리즘

버블 정렬은 인접한 두 개의 원소를 비교하고, 전체적인 순서에 맞게 두 원소를 맞바꿔줌으로써 정렬을 하게 된다.

물론 여러번의 패스를 거쳐야하만 정렬이 완료되며,

이미 정렬이 완료되었다고 하더라도, 인접한 두개의 원소만 검사하기 때문에, 

패스를 모두 거치기 전에는 계속 연산을 하게 된다. 

다음과 같은 숫자들이 있다고 가정하자.

3, 7, 2, 6, 9, 1

버블정렬을 앞의 원소부터 차례로 해 나가면

첫번째 두개의 원소는 이미 오름차순 정렬 상태이므로, 정렬할 필요가 없다.

다음 두개의 원소, 7, 2의 경우 순서가 반대로 되어있으므로 정렬,

3, 2, 7, 6, 9, 1

다음, 7, 6에 대해서 마찬가지로 정렬

3, 2, 6, 7, 9, 1

이후의 정렬 과정을 통해 첫번째 패스가 지난 이후의 상태는,

3, 2, 6, 7, 1, 9

가 되며, 패스를 여러번 거친 이후에, 오름차순 정렬이 완료된다.

위에서도 언급했듯이 버블정렬은 항상 최대의 연산을 하게 되므로, 이를 개선한 버전이 존재한다.

그것에 대해서는 다음 포스트에서 다루도록 하겠다.

코드

#include <stdio.h>

void 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);
    bubble_sort(testArr,len); // 버블 정렬 호출
}

void bubble_sort(int num[],int len){
    int i,j,tempINT;
    for(i=0; i<len-1; i++){
        for(j=0; j<len-1; j++){
            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");
}

결과