버블정렬

의미>

인접한 두 원소를 비교하여 우측의 것이 크면 위치를 바꾸고 다시 바꾼 것을 가지고 그 다음 원소와 비교. 계속 이런 식으로 비교해가며 가장 큰 값을 가장 우측에 적재. 반복이 한 번 돌 때마다 반복 대상 원소들 중 가장 값이 큰 것은 맨 우측으로 적재되며 쌓인다.​

쉽게 말해서 둘이 비교해서 원하는 것이 나오면 바로 취하고 그렇게 취한 것을 가지고 또 비교해서 필요없으면 바로 갈아치워서 결국 가장 값이 큰 것을 끝까지 위치를 바꿔가며 오른쪽까지 가져가는 것.

​​

코드예시>

#include <stdio.h>

int main(void){
	
	int array[10] = {9, 5, 6, 8, 3, 7, 10, 2, 4, 1};
	int i, j, temp;
	
	for(i = 0; i < 10; i++){
		
//		for(j = 0; j < (10 - i); j++){
		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]);
	}	
	
}

 }

시간복잡도>

N(N+1)/2

-> N^2/2 + N/2

-> N^2/2

-> N^2

= O(N^2)

 

기본적으로 선택정렬과 시간복잡도 자체는 같은데 선택정렬보다 연산시간이 더 걸린다고 함. 이유는 선택정렬의 경우 한 번의 반복 싸이클에 비교 대상이 되는 것들을 쭉 비교하고 if 절에 걸릴 때에만 값의 위치를 바꿔주는데 버블정렬의 경우에는 if절에 걸리는 경우가 너무 많아서 연산이 더 많이 들어가기 때문.