SW정리: 버블 정렬(bubble sort)

2016년 3월 12일 토요일

버블 정렬(bubble sort)

시간 복잡도

정렬 과정

첫번째 원소 부터 인접한 원소끼리 비교하여 자리를 교환하면서 마지막 자리까지 이동하는 방법

그림으로 이해하기

아래는 5개의 item이 있을때 오른 차순으로 정렬하는 방법을 나타낸다.
PASS 1

item수 N=5이면
첫번째 loop의 갯수는 다음 원소와 비교하므로 마지막 지점에서는 비교할 대상이 없어져서 N-1번 까지 loop를 돈다.

for(i=0;i<N-1;i++){
if(data[i]<data[i+1]){
swap(data[i],data[i+1])
}
}

빨간색 item은 비교 후 swap된 item을 의미한다.

PASS 2

두번째 pass에서는 마지막 item이 완료되었기 때문에 비교할 필요가 없어진다. 따라서 이전에 만든 의사 코드의 수정이 필요하다. N-2 회 만큼의 loop가 돌아야 한다.

for(i=0;i<N-2;i++){
if(data[i]>data[i+1]){
swap(data[i],data[i+1])
}
}

=> 즉 그렇다면 1,2 pass를 모두 만족하는 의사 코드는 어떻게 되는가?

PASS 3, PASS 4

전체 item N=5일때 PASS는 4까지 돌면된다. 왜냐하면 마지막 2개 남았을때까지만 하면 되기때문이다.
그럼 pass를 j라고 하면 j:0->N-1 로 만들 수 있다.

최종 의사 코드는 아래와 같습니다.

for(j=0;j<N-1;j++){
for(i=0;i<N-1-j;i++){
if(data[i]>data[i+1]){
swap(data[i],data[i+1])
}
}
}

C언어로 구현하기

C, pasted 1 second ago:

#include <stdio.h>

int gdata[] = {55,7,78,12,42};
int gN = 5;

int bubblesort(int data[],int N)
{
    int i,j,temp;
    for(j=0;j<N-1;j++){
        for(i=0;i<N-1-j;i++){
            if(data[i]>data[i+1]){
                temp = data[i];
                data[i] = data[i+1];
                data[i+1] = temp;
            }
        }
    }
}

int main()
{
    int i;
    bubblesort(gdata,gN);
    for(i=0;i<gN;i++){
        printf("%d ",gdata[i]);
    }
    printf("\n");
    return 0;
}

Output:

1	7 12 42 55 78

참고

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

SW정리