[알고리즘] 버블정렬

버블 정렬 : 옆에 있는 값과 비교해서 더 작은 값을 반복적으로 앞으로 내보내는 알고리즘

​

1 10 5 8 7 6 4 3 2 9 를 오름차순으로 정렬하시오

 

int main(void) {  
	               
	int i, j, tmp;
	int array[10] = { 1,10,5,8,7,6,4,3,2,9 };

	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9 - i; j++) {
			if (array[j] > array[j + 1]) {
				tmp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = tmp;
			}
		}
	}

	for (i = 0; i < 10; i++) {
		printf("%d\n", array[i]);
	}
	return 0;
}

 

1 10 5 8 7 6 4 3 2 9 을 정렬하기 위해서는

​

=> 10 + 9 + 8 + 7 + ... + 1

=> 55

선택 정렬과 동일한 55번의 비교연산​이 필요하다.

​

마찬가지로 시간 복잡도도

=> N * (N + 1) /2

=> O(N * N) = > O(N ^ 2)

버블 정렬의 시간 복잡도

O(N ^ 2)

​

버블 정렬과 선택 정렬의 시간 복잡도는 동일하지만

​

선택정렬은 가장 작은 값을 마지막에 앞으로 이동하는 연산 1번​만 하지만

버블 정렬은 추가로 옆에 있는 값과 비교하여

자리를 바꾸는 연산​을 해야하기 때문에 컴퓨터가 작업을 하는 양이 많아진다.

​

구현 방법은 제일 간단하지만

실제 수행 시간을 분석하면 선택정렬 보다 훨씬 느리다는 특징​을 가지고 있기 때문에

정렬 알고리즘 중에서 ​제일 비효율적인 정렬 방식이다.

​

버블 정렬의 비교 횟수와 이동 횟수

비교 횟수는 O(N ^ 2)이고

이동 횟수는 안쪽 for문에 이동이 있기 때문에

		for (j = 0; j < 9 - i; j++) {
			if (array[j] > array[j + 1]) {
				tmp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = tmp;
			}
		}

최선의 정렬이 되어있는 경우에는 0번 이동을 하지만 최악의 정렬이 역순으로 되어있는 경우에는

3(N * (N + 1) /2)번 이동하기 때문에 이동 횟수는 O(N ^ 2)이다