[알고리즘]버블 정렬(Bubble Sort)

정렬 알고리즘에는 대표적으로

병합정렬, 퀵정렬, 삽입정렬, 선택정렬, 버블정렬 등이 있습니다.

이번에는 그 중에서 제일 간단하게 구현할 수 있는 버블 정렬을 알아보겠습니다!

 

 

버블 정렬(오름차순)

버블 정렬은 앞에서부터 두수를 비교하며

가장 큰수를 찾고, 남은 수를 다시 두개씩 비교하며

그 다음으로 큰 수를 찾는 과정을 원소가 1개 남을 때까지 반복하는 정렬 알고리즘입니다.

 

시간 복잡도

위 예시에서 n = 5이므로

제일 큰 숫자인 5를 찾는데까지 4번(=n-1번)이 걸리고

다음으로 큰 숫자인 4를 찾는데까지 3번(=n-2번)이 걸립니다

총 4+3+2+1번이 걸립니다.

 

n개의 수를 정렬하는 시간은

n-1+n-2+n-3+...1이므로

((n-1)(n-2))/2 = O(n^2)입니다.

최선, 최악의 경우 모두 같은 시간복잡도를 가집니다.

 

 

 

소스코드(C++)

#include <iostream>

using namespace std;

void bubble_sort(int arr[],int n){
	int i,j;
	int temp;

	for(i = n-1;i>0;i--){ 
		for(j = 0;j<i;j++){
			if(arr[j]>arr[j+1]){ //왼쪽이 오른쪽 보다 크면 swap
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

int main(){
	int arr[5] = {3, 2, 5, 1, 4};
	int n = sizeof(arr)/sizeof(int);

	bubble_sort(arr,n); //버블정렬 수행

	for(int i = 0;i<n;i++)//출력
		cout<<arr[i];
}

이중 포문을 이용하여 왼쪽이 오른쪽보다 클 때 교환해주기만 하면 끝입니다! 

정말 간단하죠?

 

구현이 쉽다는 장점이 있지만, 다른 정렬 알고리즘에 비해 오래걸린다는 단점이 있습니다.