[알고리즘] 버블정렬(BubbleSort)

 

 

void BubbleSort(int arr[], int n) {
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < n - i - 1; k++) {
			if (arr[k] > arr[k + 1]) {
				int temp = arr[k + 1];
				arr[k + 1] = arr[k];
				arr[k] = temp;
			}
		}
	}
}

 

대표적인 O(n^2) 정렬이다.

---

[ 시간복잡도 ]

 

[ 점화식 ]

N개의 버블정렬은 

N-1개의 버블정렬 알고리즘시간에 

한 개에 대한 비교연산 N-1번만 더하면 된다.

 

따라서 위와 같이 나온다.

 

---

[ 노가다 생각해보기 ]

일단 최악의 경우를 생각해보자.

비교연산이 이중 중첩 반복문 안에 즉, for for 문 안에 있다.
그리고 비교연산에 따른 break문이나 탈출문도 없다.

이게 무슨 뜻일까

각 for문은 무조건 끝까지 돈다는 얘기이다.
그럼 for문에 따른 비교횟수는 10 9 8 7 .... 2 1 로 1씩 줄어든다.

그리고 총 데이터개수가 N개 일때
가장 많은 비교연산횟수는 N-1 이므로

이를 수식으로 나타내면 아래와 같다

그럼 (1/2(n)*(n-1) 이므로 이건 빅오로 O(n^2)라고 나타낼 수 있다!