알고리즘 / 버블 정렬

학습 강의

www.boostcourse.org/cs112/lecture/119022/

 

 

버블 정렬

 

정렬되지 않은 리스트를 오름차순/내림차순으로 정렬하기 위한 알고리즘의 하나이다. 두 개의 요소를 비교하여 정렬해나가는 방식으로 좁은 범위의 정렬에 집중한다.

 

예를 들어 아래와 같은 7개의 숫자가 임의의 순서로 나열되어 있다. 버블 정렬 알고리즘을 이용하여 오름차순으로 정렬해보자.

 

0  25  10  17  6  12  9

 

두 요소 씩 비교하여 첫 번째 요소가 두 번째 요소보다 값이 크다면 두 값을 교환하는 식으로 정렬한다. 

 

0과 25 비교 후 : 0  25  10  17  6  12  9

25와 10 비교 후 : 0  10  25  17  6  12  9

25와 17 비교 후 : 0  10  17  25  6  12  9

 

이런 식으로 숫자 끝까지 정렬 하면 다음과 같이 정렬될 것이다.

 

0  10  17  6  12  9  25

 

처음 보다는 오름차순에 가까워졌지만 아직 완전하지 않으므로, 전체 오름차순이 완성될 때 까지 동일한 작업을 반복한다.

 

 

버블 정렬 코드 예시 (C언어)

 

sort 함수에 버블 정렬 알고리즘을 구현해보았다.

 

#include <stdio.h>


void sort(int n,int array[]);
int main()
{
    int n = 7;
    int arr[7] = {0, 25, 10, 17, 6, 12, 9};
    sort(n,arr);
    
    return 0;
}

void sort(int n,int array[])
{
    for(int i = 0; i<n; i++)
    {
        for(int j = 0; j <n-i-1; j++)
        {
            if (*(array+j)>*(array+j+1))
            {
            int tmp = *(array+j);
            *(array+j) = *(array+j+1);
            *(array+j+1) = tmp;
            }
    
        }

    }
    for(int i = 0; i<n; i++)
    {   if(i!=n-1)
        {
            printf("%i, ",*(array+i));
        }
        else
        {
            printf("%i ",*(array+i));
        }
    }
}