버블 정렬(Bubble Sort)

인접한 두 원소를 비교하며 정렬하는 방법이다.
학기 초에 자주 접해서 익숙하다.

위 움짤은 마약같다.

#include <iostream>
using namespace std;

int main() {
	int tmp, arr[10] = {10,5,4,6,2,3,7,9,1,8};
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < 9 - i; j++) {
			if(arr[j] > arr[j + 1]) {
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
	for(int i = 0; i < 10; i++)
		cout << arr[i] << " ";
}

시간 복잡도는 선택정렬과 동일하다.


O(n^2) 가 된다.


하지만 선택 정렬보다 느리게 작동한다.
버블정렬은 매번 인접한 원소의 자리를 바꿔줘야 하지만 선택정렬은 배열에서 가장 작은 원소의 자리만 바꿔주면 되기 때문에 연산하는 양에서 차이가 발생한다.

위 코드에 실행 중 스왑이 안 발생할 시 break 해주면 성능을 높일 수 있다.

algorithm	average	worst	best	space
bubble	O(N^2)	O(N^2)	O(N^2)	O(1)