[알고리즘] 정렬 - 버블정렬(Bubble Sort) 쉽게 정리하기

C언어 정렬 - 버블정렬(Bubble Sort) 쉽게 정리하기

버블 정렬(Bubble Sort)은 두 인접한 원소를 검사하여 정렬하는 방법입니다. 
 
버블 정렬(Bubble Sort)은 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용되는데요. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이라고 하네요.

버블 정렬(Bubble Sort)
- 두 인접한 원소를 검사하여 정렬하는 방법
- 시간 복잡도 O(n^2)
- 코드가 단순하기 때문에 자주 사용됨 

버블 정렬 알고리즘 실행 과정 해부하기

버블 정렬 알고리즘의 실행 과정을 보도록 하겠습니다.
 
이 버블 정렬 알고리즘은 인접한 두 수를 비교해서 큰 수를 뒤로 보내는 알고리즘이라고 위에서 설명한 바 있는데요. 이번에는 실제 예제를 통해서 그 과정을 눈으로 확인해 보도록 하겠습니다.


예를 들어 아래와 같이 다섯 개의 숫자가 있다고 가정하고 과정을 설명하도록 하겠습니다.

6

4

7

9

1

에서 먼저 6, 4를 비교하여 6이 더 큰 수이므로.. 두 수의 자리를 교체합니다.
 

6

4

7

9

1

4

6

7

9

1

다시 오른쪽으로 한칸 이동해서 6, 7을 비교합니다. 여기서는 7이 크므로 교환이 없습니다.

4

6

7

9

1

 

다시 오른쪽으로 한칸 이동해서 7, 9를 비교합니다. 여기서는 9이 크므로 교환이 없습니다.

4

6

7

9

1

 

다시 오른쪽으로 한칸 이동해서 9, 1를 비교합니다. 여기서는 9가 크므로 두수를 교환합니다.
 

4

6

7

9

1

4

6

7

1

9

다시 맨 처음으로 돌아와서 4, 6을 비교합니다. 6이 크므로 다음으로 진행합니다.

4

6

7

1

9

다시 오른쪽으로 한칸 이동해서 6, 7을 비교합니다. 7이 크므로 다음으로 진행합니다.

4

6

7

1

9

4

6

7

1

9

다시 오른쪽으로 한 칸 이동해서 7, 1을 비교합니다. 7이 크므로 두 수를 교환합니다.

4

1

7

1

9

4

1

1

7

9

다시 오른쪽으로 한 칸 이동해서 7, 9를 비교합니다. 9가 크므로 다음으로 진행합니다. 

4

1

6

7

9

다시 처음으로 가서 4, 1을 비교합니다. 4가 크므로 두 수를 교환합니다.

4

1

6

7

9

1

4

6

7

9

나머지도 인접한 두 수를 비교하면서 진행합니다...
정렬이 다 되었으니 나머지 과정은 생략합니다.
 
잘 보셨나요? 위의 과정과 같이 버블 정렬이 진행됩니다.

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

버블 정렬(Bubble Sort)의 알고리즘을 분석해보도록 하겠습니다.

먼저 메모리 사용 공간을 보면 아래와 같이 n개의 원소를 저장하므로 n개의 메모리를 사용하게 됩니다.

6

4

7

9

1

그 다음으로는 연산 시간에 따른 최선, 최악의 경우를 비교해 보도록 하겠습니다.

최선의 경우는 자료가 이미 정렬되어 있는 경우입니다. 아래와 같이 정렬되어 있는 경우, 비교횟수는 i번째 원소를 (n-1)번 비교하므로 n(n-1)/2번이고 자리교환이 발생하지 않으므로 자리교환횟수는 0번입니다.

1

4

6

7

9

 
최악의 경우는 자료가 역순으로 정렬되어 있는 경우입니다.
이 경우 비교횟수는 i번째 원소를 (n-1)번 비교하므로, n(n-1)/2번이고 자리교환횟수는 i번째 원소를 (n-1)번 교환하므로 n(n-1)/2번이 됩니다.

9

7

6

4

1

 

버블 정렬 알고리즘 분석

* 메모리 사용 공간

n개의 원소에 대하여 n개의 메모리 사용

* 연산 시간

- 최선의 경우 : 자료가 이미 정렬되어 있는 경우

:: 비교횟수 : i번째 원소를 (n-1)번 비교하므로, n(n-1)/2번

:: 자리교환횟수 : 자리교환이 발생하지 않음

- 최악의 경우 : 자료가 역순으로 정렬되어 있는 경우

:: 비교횟수 : i번째 원소를 (n-1)번 비교하므로 n(n-1)/2번

:: 자리교환횟수 : i번째 원소를 (n-1)번 교환하므로 n(n-1)/2번

평균 시간 복잡도는 O(n^2)이 됨

 

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

 
 
버블 정렬(Bubble Sort) 알고리즘 소스를 보도록 하겠습니다.

 #include<stdio.h>

int main()
{
    int arr[5]={6,4,7,9,1};
    
	int i,j,tmp;
    
	// 정렬 전 배열값 출력
	printf("===== 버블정렬 전 =====\n");
    for(i=0;i<5;i++) printf("%3d",arr[i]);
	printf("\n");

	// 버블정렬
	for(i=0;i<5;i++) 
    {
        for(j=0;j<4;j++)
        {
			// 앞의 수, 바로 뒤의 수 비교해서
			// 앞의 수가 클 경우 값을 교환
            if(arr[j]>arr[j+1])
            {
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }

	// 버블 정렬 결과 출력
	printf("===== 버블정렬 후 =====\n");
    for(i=0;i<5;i++) printf("%3d",arr[i]);
	printf("\n");

	return 0;   
}

위의 소스를 실행한 결과입니다.

위 소스의 핵심소스는 아래 부분이 되겠습니다.

 

// 버블정렬
	for(i=0;i<5;i++) 
    {
        for(j=0;j<4;j++)
        {
			// 앞의 수, 바로 뒤의 수 비교해서
			// 앞의 수가 클 경우 값을 교환
            if(arr[j]>arr[j+1])
            {
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
        }
    }

궁금하신 것이 있으시면 댓글 남겨주세요^^