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

버블 정렬 (Bubble Sort)이란?

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

 Process 

① 1회전에서 첫 번째 원소부터 시작. 첫 번째 원소와 두 번째 원소를 비교하여 첫 번째 원소가 더 크면 두 원소의 자리를 교환한다. 그리고 두 번째 원소를 세 번째 원소와, 세 번째 원소를 네 번째 원소와, ... N - 1 번째 원소를 N 번째 원소와 비교와 교환을 반복한다.

② 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하기 때문에, 2회전에서는 맨 마지막 원소를 제외하고 비교하면 된다. 이렇게 1회전 수행할 때마다 뒤에서 하나씩 비교 대상에서 제외된다.

 

 Code 

void BubbleSort(int DataSet[], int Lenght)
{
    int temp = 0;
    for(int i = 0; i < Lenght; i++)
    {
        for(int j = 1; j < Lenght - i; j++)
        {
            if(DataSet[j-1] > DataSet[j])
            {
                temp = DataSet[j-1];
                DataSet[j-1] = DataSet[j];
                DataSet[j] = temp;
            }
        }
    }
}

 시간복잡도 

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n (n-1) / 2 이므로  O(n^2)이다.

정렬이 되어 있던, 안되어 있던 비교하기 때문에 최선, 최악, 평균의 시간복잡도가 모두 동일하다.

 공간복잡도 

주어진 배열 안에서 교환하기 때문에, O(n)이다.

 장점 

- 구현이 간단하고 소스가 직관적이다.

- 정렬하고자 하는 배열 안에서 교환하기 때문에, 다른 메모리 공간을 필요로 하지 않는다 => 제자리 정렬(in-place sorting)

- 안정 정렬(Stable Sort)이다.

 단점 

- 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.

- 교환 연산이(swap)이 많이 일어난다.

 

 정렬 알고리즘 시간 복잡도 비교