버블정렬 (Bubble Sort)

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요. 

1 10 5 8 7 6 4 3 2 9

---

버블정렬 

가까이에 있는 두 숫자끼리 비교해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다.

 

---

코드 및 풀이 (with c언어)

#include <stdio.h>

int main(void) {
	int i, j, temp; 
	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]) {
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp; 
			}
		}
		
	}
	for (i = 0; i < 10; i++){
		printf("%d ", array[i]);
	}

	return 0;
}

단순히 반복적으로 두 숫자를 비교하여 앞으로 보낸다. 

temp를 통해 두 숫자를 비교하여 위치를 바꿔주는 역할을 한다. 

이 과정을 통해서 각 싸이클마다 가장 큰 값이 맨 뒤로 보내지게 된다.  

---

실행결과

 

 

실행결과를 봤을 때 오름차순으로 정렬이 잘 일어난 것을 볼 수 있다. 

 

버블 정렬은 컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어

실제 수행시간이 가장 느린 안 좋은 알고리즘이라고 할 수 있다. 

 

시간 복잡도는 선택 정렬과 동일하게 일어나지만 선택 정렬보다 효율이 더 떨어지는 알고리즘이라고 할 수 있다. 

버블 정렬의 시간 복잡도는 O(N^2)이다.