[알고리즘] Bubble Sort

오름차순 정렬 코드 예시

//N은 배열에 넣은 값의 총 갯수
void bubble_sort(int arr[], int N) {
	int temp;
    // 총 회전은 N-1번
	for(int i = N-1; i>0; i--) {
    	//1회전 당 i번
		for(int j = 0; j<i; j++) {
			if(arr[j] > arr[j+1]) {
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

 

배열에 넣어준 값에 갯수가 N개일 때

 

총 N-1 회전을 갖고

각 회전 당 1회전은 N-1번, 2회전은 N-2번 ... N-1회전은 1번. 이렇게 이어지게 됌.

1회전   : N - 1
2회전   : N - 2
3회전   : N - 3
.
.
.
N-2회전 : 2
N-1회전 : 1

 

따라서 총 횟수는 (N-1) + (N-2) + .... + 1 = n(n-1)/2 번.