[C/C++] 버블 정렬(bubble sort) 알고리즘으로 올림차순 구현하기

버블 정렬이란?

버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내는 정렬하는 방식입니다.

 

버블 정렬은 가장 무식하고 비효율적인 알고리즘 중 하나이지만 가장 직관적이고 구현하기 쉬운 알고리즘입니다.

 

예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다.

값	5	6	10	4	3	8	7	1	2	9
위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

 

먼저 5와 6을 비교하였을 때 뒤에 있는 6이 더 큰 숫자이므로 교환이 일어나지 않습니다.

다음은 6과 10을 비교하였을때 뒤에 있는 10이 더 큰 숫자이므로 역시 교환이 일어나지 않습니다.

다음은 10과 4를 비교하였을때 앞에 있는 10이 더 큰 숫자이므로 두 숫자는 교환이 일어납니다.

 

값	5	6	4	10	3	8	7	1	2	9
위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

 

이런 식으로 [9] 번 인덱스까지 진행하게 되면 가장 큰 수인 10이 [9] 번 인덱스로 이동하게 되어 [9] 번 인덱스는 정렬이 끝나게 됩니다.

 

다시 [0]번 인덱스부터 [8] 번 인덱스까지 반복하게 되면 [8] 번 인덱스는 정렬이 끝나게 됩니다. 이런 방식을 10번 반복하게 되면 정렬이 끝나게 됩니다.

 

즉, 처음은 0~9까지, 두 번째는 0~8까지 세 번째는 0~7까지 . . .

 

다음은 C언어로 버블 정렬은 구현한 예입니다.

 

#include <stdio.h>

int main(){
	//1~10 무작위 배열
	int arr[10] = {5, 6, 10, 4, 3, 8, 7, 1, 2, 9};
	int i, j, temp;
	
	for(i=0;i<10;++i){
		for(j=0;j<10-i-1;++j){
			//옆에 있는 수와 비교하여 앞에수가 크다면 교환 
			if(arr[j]>arr[j+1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
	
	//출력 
	for(i=0;i<10;++i){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

결과값:

1 2 3 4 5 6 7 8 9 10

 

올림차순으로 정렬이 된 것을 확인할 수 있습니다. 

 

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