3. 버블 정렬(Bubble Sort)

ㆍ가장 효율성이 떨어지는 알고리즘.

ㆍ당장 옆에 있는 것과 비교해서 둘끼리만 이동.

ㆍ 수행 시간 : n x (n+1) / 2

ㆍ선택정렬처럼 시간복잡도는 O(N^2)으로 동일하지만, 자리를 바꾸는 연산이 계속 이루어지기 때문에 선택정렬보다도 훨씬 느리다. 정렬 알고리즘중에 가장 느리다.

 

#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++) {		//i를 10번
		for (j = 0; j < 9 - i; j++) {	//j를 9번(집합의 크기가 하나씩 감소되기 때문
			// j 위치 > 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;
}

 

출력 결과