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

버블 정렬(Bubble Sort)

• 버블 정렬 알고리즘은 가장 기초적인 정렬 알고리즘이다.
• 핵심 아이디어는 “인접한 두 원소를 비교해서 큰 값을 뒤로 보내는 방식”이다.
• 한 번 순회를 수행하면 가장 큰 값이 배열의 끝으로 이동하는 것이 마치 물 속의 거품(bubble)이 위로 떠오르는 것 같아서 Bubble Sort라는 이름이 붙었다.

	1회전 [17, 3, 29, 6, 10] : (17, 3) 비교 → 17 > 3이므로 교환 [3, 17, 29, 6, 10] : (17, 29) 비교 → 교환 없음 [3, 17, 29, 6, 10] : (29, 6) 비교 → 29 > 6이므로 교환 [3, 17, 6, 29, 10] : (29, 10) 비교 → 29 > 10이므로 교환 가장 큰 값인 29가 맨 뒤로 이동한다.
	2회전 [3, 17, 6, 10, 29] : (3, 17) 비교 → 교환 없음 [3, 17, 6, 10, 29] : (17, 6) 비교 → 17 > 6이므로 교환 [3, 6, 17, 10, 29] : (17, 10) 비교 → 17 > 10이므로 교환
	3회전 [3, 6, 10, 17, 29] : (3, 6) 비교 → 교환 없음 [3, 6, 10, 17, 29] : (6, 10) 비교 → 교환 없음
	4회전 [3, 6, 10, 17, 29] : (3, 6) 비교 → 교환 없음 정렬 완료

 

C++을 이용하여 Bubble Sort 구현

void bubble_sort(int arr[], int n) {
	for(int i = 0; i < n-1; i++) {
		for(int j = 0; j < n-i-1; j++) {
			if(arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
	}
}

 

시간 복잡도

버블 정렬은 모든 원소를 반복적으로 비교한다.

비교 횟수: $$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$$

 

따라서 시간 복잡도는 \(O(n^2)\)이다.