버블 정렬 (Bubble Sort)

1. 버블 정렬

2개씩 비교해서 더 작은 것을 앞으로 자리바꿈

  * 세로로 그려 보면, 가장 작은 것이 거품처럼 위로 (=맨 앞으로) 올라가는 형태 

 

 

[ Algorithm ]

1. for pass = 1 to n-1
2. for i = 1 to n-pass
3. if (A[i-1] > A[i]) // 위의 원소가 아래의 원소보다 크면
4. A[i-1] ↔ A[i] // 자리바꿈
5. return A

 

 

 

2. 버블 정렬 예제

ex )  1  10  5  8  7  6  4  3  2  9  오름차순 정리하시오.

 

#include <stdio.h>

int main(void) {
	int a[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
	int n = sizeof(a) / sizeof(int);
	int temp;

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


	}

	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}

}

 

 

 

3. 버블 정렬의 시간 복잡도

앞의 예제에서 총 비교 횟수를 대략적으로 살펴보면 다음과 같다. 

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 +1 = 10 * (10 +1) / 2

 

∴  input이 N개일 때, 버블 정렬의 시간복잡도는 O(N^2) 

 

다만, 버블 정렬은 매번 2개 비교할 때마다 자리 바꿔줘야 해서 선택 정렬보다 실제 수행시간 더 느림!