거품 정렬(Bubble sort)

- 두 인접한 원소를 검사하여 정렬하는 방법
- 속도는 느리지만 코드가 단순해 자주 이용됨
- 원소의 이동이 거품이 수면으로 올라오는 듯한 모습

소스 (오름 차순)

void bubble(char *arr, int len)
{
int i,j;
char temp;

printf("Before Sorting : %s\n",arr);

    for(i=0;i<len-1;i++){
       for(j=0;j<len-1;j++){
            if(arr[j]>arr[j+1])
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }

printf("After Sorting : %s\n",arr);
}

소스(내림 차순)

void bubble(char *arr, int len)
{
int i,j;
char temp;

printf("Before Sorting : %s\n",arr);

    for(i=0;i<len-1;i++){
       for(j=0;j<len-1;j++){
            if(arr[j]<arr[j+1])
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }

printf("After Sorting : %s\n",arr);
}

오름 차순 내림 차순

버블 정렬은 위와 같이 간단하게(?) 구현이 가능하다.

하지만, 문제점이 발생한다. 반복 for문 에서 필요 없는 작업을 수행할 경우가 발생한다.

예를 들면

위와 같이 1 2 3 의 숫자를 오름차순을 이용한 버블 정렬을 할 경우 한번의 비교만으로

끝나는 작업이지만 위의 알고리즘은 문자의 길이만큼인 3번을 수행한다.

불필요한 작업이 발생한다(설명하기 어렵군요..)

flag를 사용하면 이를 예방할 수 있다.

소스

void bubble(char *arr, int len)
{
    int i,j;
    char temp;
    int flag =1;

printf("Before Sorting : %s\n",arr);

for(i=0;i<len-1 && flag ==1;i++){

flag =0;

        for(j=0;j<len-1;j++){
            if(arr[j]>arr[j+1])
            {
                flag =1;
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
        printf("%dcycle, After Sorting : %s\n",i+1,arr);
    }

}

간단하게 소스를 설명 하면 ,

flag 변수를 추가해서 초기 값을 1을 설정합니다.

첫번째 for문에 밑에서 flag 값을 0을 대입 합니다.

if 조건에 해당하는 경우(즉, 원소의 이동이 있을 경우 )flag에 1을 대입해

첫번째 for문이 계속 수행됩니다.

만약에 if 조건(원소의 이동)없을 경우 flag값은 0을 유지하게 됩니다.

flag값이 0이 되면 첫 번째 for문 조건에서 &&(AND 연산자)에 의해서

len-1 && flag==1 값이 0이 되면서 for문을 빠져 나오게 됩니다.

마치며,

새벽 2시입니다. 미숙한 포스팅 실력으로 글의 질이 현저하게 떨어 지리라 생각 됩니다.

윈도우 라이브 라이터를 이용해서 글을 올리다가 몇 번 날려 버리고 잠자리에 누웠다가

잠이 안와서 다시 이렇게 다시 올리고 있습니다. 부족한 글 읽어주셔서 감사합니다.

잘못된 부분이 있을 수도 있습니다. 비판적인 자세로 읽어주세요^^

거품 정렬(Bubble sort)

티스토리툴바