[알고리즘] 버블 정렬(Bubble sort)의 개념 with c++

버블 정렬은 인접한 두 수를 계속해서 비교하여 정렬하는 알고리즘이다. 

 

1. 인접한 두 수를 대소를 비교한다.

2. 내림차순, 오름차순에 따라 두 수의 자리를 바꾼다.

3. 나머지 값들도 동일하게 처리한다.

 

구현이 매우 간단하여 코드 구현이 쉽지만, 비교 작업이 많기 때문에 시간 복잡도(n^2) 로 오래걸린다는 단점이 있다.

적은 양의 데이터를 정렬할때는 버블 정렬을 쓸 수 있지만, 대용량의 데이터를 정렬시 엄청 시간이 소요될 것이다. 

 

 

무작위 배열수의 버블 정렬 (wikipedia)

📌 버블 정렬 c++ 코드 구현

#include<stdio.h>

using namespace std;

int main(){

	//버블정렬-오름차순 
	
	int n, i,j, tmp, a[101];
	
	scanf("%d", &n);
	
	for(i=0; i<n; i++){
		scanf("%d ",&a[i] );
	}
	
	for(i=0; i<n-1; i++){
		for(j=0; j<n-i-1; j++){
			if(a[j]>a[j+1]) {
				tmp=a[j];
				a[j]=a[j+1];
				a[j+1]=tmp;
			}
		}
	}
	
	for(i=0; i<n; i++){
		printf("%d ",a[i] );
	}
	
	return 0;	
}