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

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

 

버블 정렬은 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬입니다.

 

1   9   4   6   11   10   3   15   2   13

 

위와 같은 수가 있을 때 수들을 오름차순하는 버블 정렬을 해보겠습니다.

 

먼저 배열의 맨 앞부터 두 수씩 비교합니다. 1과 9를 비교하여 1이 더 작으므로 1을 정렬합니다.

그 다음 9와 4를 비교하여 4가 더 작으므로 9와 4의 위치를 교환하고 4를 정렬합니다.

그 다음 9와 6을 비교하여 6이 더 작으므로 9와 6의 위치를 교환하고 6를 정렬합니다.

그 다음 9와 6을 비교하여 6이 더 작으므로 9와 6의 위치를 교환하고 6를 정렬합니다.

 

1   9   4   6   11   10   3   15   2   13

1   4   9   6   11   10   3   15   2   13

1   4   6   9   11   10   3   15   2   13

1   4   6   9   11   10   3   15   2   13

. . . 

1   4   6   9   10   3   11   2   13   15

 

위와 같은 방식으로 1차 버블 정렬을 끝나면 가장 큰 수인 15의 정렬이 확정됩니다. 이후 정렬이 확정된 데이터를 제외한 나머지 배열에서 2차 버블 정렬을 수행합니다

 

1   4   6   9   10   3   11   2   13   15

1   4   6   9   3   10   2   11   13   15

 

2차 버블 정렬이 끝나면 가장 큰 수인 13의 정렬이 확정됩니다. 이러한 방식으로 1차, 2차, 3차 . . . 반복하여 정렬하는 방식이 버블 정렬입니다.

 

알고리즘 구현

// Algorithm Analysis
// 버블 정렬(Bubble Sort) : 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보낸다.

#include <stdio.h>
#include <stdlib.h>

int main() {
	int i, j, temp;
	int arr[10] = { 1, 9, 4, 6, 11, 10, 3, 15, 2, 13 };
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < 10; i++)
		printf("%d ", arr[i]);

	return 0;
}

 

시간 복잡도 : O(N * N)

버블 정렬 알고리즘의 시간 복잡도는 O(N * N) 로 선택 정렬과 삽입 정렬과 같은 복잡도를 보이나 연산 수가 가장 많아 정렬 알고리즘 중에서 상대적으로 가장 느리고 효율성이 떨어지는 정렬 방식입니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.