[알고리즘] 버블 정렬(Bubble Sort)

버블 정렬이란

두 인접한 원소를 검사하여 정렬하는 방법입니다. 쉽게 말해, 옆 인덱스와 비교를 하여 값이 더 큰 데이터를 앞이나 뒤로 보내는 정렬 방법입니다. 버블 정렬은 그림에서 보듯이 거품이 올라오는 것처럼 보인다고 하여 버블 정렬이라고 불립니다.

버블 정렬

버블 정렬

위 그림은 버블 정렬의 정렬 방법 및 순서를 나타낸 것입니다. 

왼쪽 인덱스의 데이터가 오른쪽 인덱스의 데이터보다 크다면 스왑 하여 큰 수를 뒤로 보내는 방식을 반복합니다.

버블 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 인덱스가 n 개라고 했을 때 O(n^2)이 나옵니다. 그래프에서는 청록색입니다. 따라서 버블 정렬 또한 n의 값이 커질수록 걸리는 시간이 기하급수적으로 늘어나므로 비효율적인 정렬 알고리즘입니다.

 

<C언어 코드>

#include <stdio.h>
 
void BubbleSort(int data[], int size)
{
    int temp = 0;
    //for문이 size - 1인 이유는 인덱스를 2개씩 검사를 할때 해당 인덱스와 다음 인덱스를 검사하기 때문에
    //마지막 인덱스의 직전 인덱스까지만 검사를 해도 모든 인덱스를 검사하는 것이 된다.
    for (int i = 0; i < size - 1; i++)
    {
        //i를 빼주는 이유는 회전할 때마다 큰 수대로 뒤에서 부터 정렬이 되기 때문이다.
        for (int j = 0; j < size - i - 1; j++)
        {
            //왼쪽 인덱스가 오른쪽 인덱스보다 크다면 스왑
            if (data[j] > data[j + 1])
            {
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
}
 
int main()
{
    int arr[10] = { 1, 5, 7, 9, 2, 3, 6, 4, 0, 8 };
 
    BubbleSort(arr, 10);
 
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
 
    return 0;
}