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

■ 버블 정렬(Bubble Sort)

버블 정렬이란 이름은 큰 값이 뒤로 떠오르는 모습이 마치 물속에서 거품(버블)이 위로 올라가는 것처럼 보인다는 데서 유래된 이름이다.

[버블 정렬의 원리]

버블 정렬은 인접한 두 개의 원소를 비교하는 방식으로 정렬을 수행한다. 현재 탐색 중인 요소의 인덱스 번호를 $n$이라 한다면,

1. arr[n] > arr[n+1] 이라면, 두 원소의 값을 서로 교환한다. (오름차순 정렬 기준)
2. 위 비교는 “$n + 1 <$ 배열의 길이 - 현재 회차 - 1”을 만족하는 동안 반복된다.

즉, 첫 번째 반복이 끝나면 배열에서 가장 큰 값이 맨 뒤에 위치하게 된다. 두 번째 반복이 끝나면 두 번째로 큰 값이 그 앞자리에 위치하게 된다.

• 이렇게 반복이 진행될수록 가장 큰 값이 점차 뒤쪽으로 이동하게 되는 알고리즘이다.

 

■ 버블 정렬 구현(C#)

버블 정렬의 구현 방법은 매우 간단하다.

이중 for문을 사용해서 구현하며, 가장 바깥쪽 반복문이 한 번 수행될 때마다 가장 큰 값이 배열의 끝으로 이동하게 된다.

public static class SortArray<T> where T : IComparable<T>
{
    // 버블 정렬
    public static void BubbleSort(T[] arr)
    {
        for(var i = 0; i < arr.Length - 1; ++i)
        {
            for(var j = 0; j < arr.Length - i - 1; ++j)
            {
                if (arr[j].CompareTo(arr[j + 1]) > 0)
                {
                    var temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

위 구현에선 제너릭 형식을 사용하여, 모든 비교 가능한 타입(IComparable 인터페이스를 구현한 타입)에 대해 정렬이 가능하도록 했다.

버블 정렬은 매 반복 회차마다 가장 큰 값을 뒤로 보내는 방식이기 때문에, 이미 정렬이 완료된 요소는 이후 비교 대상에서 제외해도 된다.

• 안쪽 반복문의 조건을 j < arr.Length - i - 1로 설정하여, 매 회차마다 비교 범위를 줄여 나간다.

 

▶ 버블 정렬의 시간복잡도

버블 정렬은 이중 for문으로 구성되어 있는데, 바깥쪽 반복문은 입력 데이터의 개수$(n)$만큼 반복된다. 반면 안쪽 반복문은 반복이 진행될수록 실행 횟수가 점차 줄어드는($n-m$) 구조를 가지고 있다.

• $i = 0$ 이면, $j$는 0부터 $n-1$까지 ⇒ 총 $n-1$회 실행.
• $i = 1$ 이면, $j$는 0부터 $n-2$ 까지 ⇒ 총 $n-2$회 실행.
• ……
• $i = n-2$ 이면, $j$는 0부터 0까지 ⇒ 총 1회 실행.

그렇다면, 총 반복 횟수는 다음과 같이 계산 가능하다.

$$ (n-1) + (n-2) + (n-3) + ... + 1 = \frac{n(n-1)}{2} = \frac{n^2 -n}{2} $$

[등차수열의 합 공식]

 

하지만 빅-오 표기법에선? 가장 영향력이 큰(최고 차항의 계수)만 고려하므로, 버블 정렬의 시간복잡도는 결국 $O(n^2)$이 된다.