[Algorithm#02] | 버블 정렬(Bubble Sort)

🎓 동빈나님의 강의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 듣고 정리한 내용입니다.

 

💻 알고리즘

버블 정렬(Bubble Sort)

• "옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내면 어떨까?"
• 버블 정렬 또한 선택 정렬과 같이 몹시 직관적인 해결 방법입니다. 바로 가까이에 있는 두 숫자끼리 비교를 해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 겁니다.
• 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법입니다.
• 구현은 가장 쉽지만 가장 비효율적인 알고리즘

 

📝 문제

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

 

✏️ 소스 코드

#include <stdio.h>

int main(void)
{
    int i, j, temp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

    for (i = 0; i < 10; i++)
    {// 원소의 개수만큼 반복
        for(j = 0; j < 9 - i; j++)
        {// 조건식이 "< 9 - i"인 이유 -> 반복마다 뒤에서부터 집합의 원소를 하나 씩 지우기 때문 
            if(array[j] > array[j + 1])
            { // 반복할 때 마다 당장 옆의 값과 비교하여 왼쪽의 값이 오른쪽의 값보다 크다면 
                // Swaping
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    for(i = 0; i < 10; i++)
    {
        printf("%d ", array[i]);
    }
    return 0;
}

 

⏳ 시간 복잡도

버블 정렬의 시간 복잡도는 O(N^2)입니다.

 

📚 참고 사이트

• 동빈나 블로그
• 동빈나 - 실전 알고리즘 강좌 (Algorithm Programming Tutorial)