버블 정렬(Bubble Sort)

 

버블 정렬은 바로 다음에 있는 값과 비교해서 정렬하는 알고리즘입니다.

 

2, 5, 6, 4, 1, 10, 9, 8, 3, 7

위의 숫자 10개를 오름차순으로 하여 예로 들자면 

1. 0번째 인덱스와 1번째 인덱스를 비교해보니 0번째 인덱스가 더 작다.

2. 서로 바꾸지 않는다.

 

3. 1번째 인덱스와 2번째 인덱스를 비교해보니 1번째 인덱스가 더 작다.

4. 서로 바꾸지 않는다.

 

5. 2번째 인덱스와 3번째 인덱스를 비교해보니 3번째 인덱스가 더 작다.

6. 2번째 인덱스와 3번째 인덱스를 서로 바꾼다.

 

2, 5, 4, 6, 1, 10, 9, 8, 3, 7

1. 3번째 인덱스와 4번째 인덱스를 비교해보니 4번째 인덱스가 더 작다.

2. 3번째 인덱스와 4번째 인덱스를 서로 바꾼다.

 

2, 5, 4, 1, 6, 10, 9, 8, 3, 7

                          .

                          .

                          .

 

이런식으로 쭉 갑니다.

이런식으로 진행을 하면 제일 큰 수는 제일 뒤로 밀리기 때문에 

정렬은 맨 마지막부터 완료가 됩니다.

 

C언어로 작성한 소스는 다음과 같습니다.

#include<stdio.h>
int main()
{
	int temp; //임시로 값을 저장할 변수
	int array[10]={2,5,6,4,1,10,9,8,3,7};
	
	for(int i=0; i<10; i++) //배열의 처음부터 시작 
		for(int j=0; j<9-i; j++) // 정렬은 맨 마지막에서부터 완료되서 9-i가 됨
			if(array[j]>array[j+1]) // 오름차순 정렬이라 내것이 더 크면 실행해야함 
			{ // 바로 다음 값과 바꾸는 코드
				temp = array[j]; 
				array[j] = array[j+1];
				array[j+1] = temp;
			} 
		
	for(int i=0; i<10; i++)
		printf("%d ",array[i]);
	
	return 0;
}

 

소스코드를 좀 변형해서 중간과정을 출력해보면 다음과 같습니다.

                                                버블 정렬의 시간 복잡도는 O(N^2)입니다.