[알고리즘] 버블 정렬

버블 정렬

: 인접한 두 개의 원소를 비교하여 자리 교환하는 방식. 첫 번째 원소부터 마지막 원소까지 반복하면 가장 큰 원소가 마지막 자리에 온다. 

 

시간복잡도

• 비교 횟수
  • 최상, 평균, 최악 모두 일정.
  • n-1, n-2, … , 2, 1 번 = n(n-1)/2
• 교환 횟수
  • 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
  • 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
• O(n^2)

C언어 구현

void bubbleSort(int A[], int n) {
	int temp;
	for (int i = n - 1; i >= 1; i--) {
		for (int j = 0; j < i; j++) {
			if (A[j] > A[j + 1]) {
				temp = A[j + 1];
				A[j + 1] = A[j];
				A[j] = temp;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", A[i]);
	}
}