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

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

버블 정렬(Bubble Sort)이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

 

배열 A[N]이 있을 경우 배열의 원소 A[n]과 ~ A[n+1]을 순차적으로 비교하며 가장 큰 수를 맨 뒤로 이동하는 방법이다.

가장 큰 자료가 맨 뒤로 이동하므로 맨 끝 원소는 검사 및 정렬에서 제외된다. 반복횟수마다 검사하는 원소가 줄어드는 이유이다.

 

5개의 원소 안에 {5, 3, 1, 4, 2} 의 원소가 들어가 있을 경우 버블 정렬은 아래 그림과 같다.

1회차

   - 5와 3을 비교 후 자리를 바꾼다.

   - 5와 1을 비교 후 자리를 바꾼다.

   - 5와 4를 비교 후 자리를 바꾼다.

   - 5와 2를 비교 후 자리를 바꾼다.

   - 마지막 자리수는 이제 검사할 필요가 없다.

2회차

   - 3과 1을 비교 후 자리를 바꾼다.

   - 3과 4를 비교했지만 자리를 바꿀 필요가 없다.

   - 4와 2를 비교 후 자리를 바꾼다.

   - 4가 들어있는 곳도 이제 검사할 필요가 없다.

3회차

   - 1과 3을 비교했지만 자리를 바꿀 필요가 없다.

   - 3과 2를 비교 후 자리를 바꾼다.

   - 3의 자리는 검사에서 제외된다.

4회차

   - 1과 2를 비교했지만 자리를 바꿀 필요가 없다.

   - 정렬 완료.

 

다음은 C++ 코드를 활용해 작성한 버블 정렬의 참고용 슈도 코드이다.

 

void bubble_sort(int A[], int n)
{
	int temp;
	for(int i = 1; i < n; i++)	// 회차
    {
    	for(int j = 0; j < n-i; j++)	// 마지막 원소 검사는 제외 (n-1번 반복)
        {
        	if(A[j] > A[j+1])	// A[j]와 그 다음 원소 A[j+1]을 비교하기 위한 구문
            {
            	temp = A[j];
                A[j] = A[j+1];
                A[j+1] = temp;
            }
        }
    }
}

 

버블 정렬은 구현이 매우 간단하지만 자료의 교환 작업은 이동 작업보다 복잡하기 때문에 실무에서는 권유하지 않는 방법이다.

시간 복잡도는 O-표기법으로 했을 때 O(n^2) 이다.