[정렬] 버블정렬(Bubble Sort) C언어

정렬 방법

인접한 두 원소의 크기를 비교해 순서대로 되어 있지 않으면 교환한다.

 

속도

시간복잡도가 언제나 O(n^2)이므로, 정렬속도는 느리다.

 

예시

다음과 같이 정렬되지 않은 배열 arr[4] = {2, 4, 9, 1}을 오름차순으로 정렬해보자.

<1>

arr[0]	arr[1]	arr[2]	arr[3]
2	5	9	1

우선 첫번째 원소와 두번째 원소를 서로 비교한다.

arr[0] < arr[1] 이므로 교환하지 않는다.

마찬가지로 arr[1] < arr[2] 이므로 서로 교환하지 않는다.

arr[2] > arr[3] 이므로 서로 교환해주면 다음과 같이 된다.

arr[0]	arr[1]	arr[2]	arr[3]
2	5	1	9

여기까지가 1회전이다.

 

<2>

1회전에서 가장 큰 수가 오른쪽에 정렬되었으므로, 마지막 원소는 비교할 필요가 없다.

arr[0] < arr[1]

arr[1] > arr[2] -> 교환

arr[0]	arr[1]	arr[2]	arr[3]
2	1	5	9

 

<3>

arr[0] > arr[1] -> 교환

arr[0]	arr[1]	arr[2]	arr[3]
1	2	5	9

 

원소개수 -1만큼 실행한다.

각 회전을 돌 때마다 비교횟수가 1씩 감소한다.

 

 

C언어로 구현

#include <stdio.h>
#define size 6
int main(void){
	int arr[size] = {2, 5, 9, 1, 7, 3};
	int i, j, temp;
	for(i=0; i<size-1; i++){
		for(j=0; j<size-1-i; j++){
			if(arr[j] > arr[j+1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
	return 0;
}

정렬과정

2 5 9 1 7 3
2 5 9 1 7 3
2 5 1 9 7 3
2 5 1 7 9 3
2 5 1 7 3 9
2 5 1 7 3 9
2 1 5 7 3 9
2 1 5 7 3 9
2 1 5 3 7 9
1 2 5 3 7 9
1 2 5 3 7 9
1 2 3 5 7 9
1 2 3 5 7 9
1 2 3 5 7 9
1 2 3 5 7 9

 

 

함수

#include <stdio.h>
#define size 6
void bubbleSort(int array[size]){
	int i, j, temp;
	for(i=0; i<size-1; i++){	
		for(j=0; j<size-1-i; j++){		
			if(array[j] > array[j+1]){	
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
	}
}
int main(void){
	int arr[size] = {2, 5, 9, 1, 7, 3};
	bubbleSort(arr);  
	int i;
	for(i=0; i<size; i++)	printf("%d ", arr[i]);	
	return 0;
}

사용하기 편하게 함수로 만들어보았다.