[Algorithm] 버블 정렬(Bubble Sort)

 

버블 정렬(Bubble Sort)

바로 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 정렬법(반복)

 

- 선택 정렬과 같이 직관적인 알고리즘

- 가장 비효율적인 정렬 알고리즘

- 데이터의 개수가 조금만 많아지더라도 아주 많은 연산을 해야하기때문에 시간이 오래걸림

 

---

예제) 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.

1 10 5 8 7 6 4 3 2 9

 

1) 한번의 반복이 끝나면 가장 큰 값이 뒤로 보내지는 정렬법

1 10 5 8 7 6 4 3 2 9

1 5 10 8 7 6 4 3 2 9

1 5 8 10 7 6 4 3 2 9

1 5 8 7 10 6 4 3 2 9

1 5 8 7 6 10 4 3 2 9

1 5 8 7 6 4 10 3 2 9

1 5 8 7 6 4 3 10 2 9

1 5 8 7 6 4 3 2 10 9

1 5 8 7 6 4 3 2 9 10

....(중략)

 

#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++){
		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]);
	}

	return 0;
}

 

---

버블 정렬의 시간 복잡도는 O(N^2) -> 최대한 피해야하는 시간 복잡도

 

버블 정렬은 얼마나 많은 시간을 잡아먹을까?

10 + 9 + 8 + ... + 2 + 1

-> 등차수열 

-> 10*(10+1)/2=55

-> 10개를 계산하기 위해 최소한 55번의 연산 필요 

-> 굉장히 비효율적인 알고리즘 정렬.....

-> 옆에 있는 원소와 계속 해서 비교하고 매번 자리를 교체하기때문에 선택 정렬보다 더 오래걸림...

 

=> N*(N+1)/2

=> N*N

 

 

 

빅오표기법 : 특정한 알고리즘의 수행시간 표기

O(N*N) = O(N^2)

 

 

---

출처 및 참고

https://blog.naver.com/ndb796/221226800661