[알고리즘] 버블 정렬 알고리즘

1. 정의

- 버블 정렬(Bubble Sort)은 배열을 순차적으로 검사하여 인접한 두 원소가 오름차순 정렬에 맞지 않으면 이들을 서로 교환하는 정렬 알고리즘이다. 즉, 먼저 a[1]과 a[2]를 비교하여 정렬 순서에 맞지 않으면 서로 교환한다. 이 작업을 배열의 끝까지 반복하여 더이상의 교환이 없을 때 정렬을 마무리 한다.

2. 알고리즘

BubbleSort(a[n], n)

for(i <- n; i >= 1; i <- i -1) do {

for(j <-1; j < i; j <0 j + 1) do {

if(a[j] > a[j + 1]) then A[j]와 a[j + 1]을 교환;

}

}

end BubbleSort()

3. 동작 과정

패스	테이블	비교값
1	[9,1,6,8,4,3,2,0]	9 > 1
	[1,9,6,8,4,3,2,0]	9 > 6
	[1,6,9,8,4,3,2,0]	9 > 8
	[1,6,8,9,4,3,2,0]	9 > 4
	[1,6,8,4,9,3,2,0]	9 > 3
	[1,6,8,4,3,9,2,0]	9 > 2
	[1,6,8,4,3,2,9,0]	9 > 0
	[1,6,8,4,3,2,0,9]	완료

패스	테이블	비교값
2	[1,6,8,4,3,2,0,9]	8 > 4
	[1,6,4,8,3,2,0,9]	8 > 3
	[1,6,4,3,8,2,0,9]	8 > 2
	[1,6,4,3,2,8,0,9]	8 > 0
	[1,6,4,3,2,0,8,9]	완료

.

.

.

- 위 작업을 반복 수행해주면 정렬이 완료되고, 더이상의 교환이 없게되면 정렬을 마무리하게 된다.

- 마치 거품이 일어나는 것 같다고 해서 버블 정렬이다.

4. 특성

(1) 시간 복잡도

- 버블 정렬 알고리즘은 N개의 원소 각각 N-1번의 비교를 해야 하기 때문에 전체 비교 횟수가 N(N-1) / 2가 되어 시간 복잡도는 O(N^2)이 된다.

- 레코드의 교환이 계속해서 일어나므로 레코드의 크기가 클 경우 불리하다.

(2) 입력 순서 민감도

- 거의 정렬된 화일의 경우 레코드의 교환이 없으므로 유리하다. 

(3) 제자리 정렬 여부

- 추가적인 기억장소를 요구하지 않으므로 제자리 정렬이다.

(4) 안정성

- 변경 후 레코드의 위치를 알 수 있으므로 안정적인 알고리즘이다.

5. 소스코드 (C언어)

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