[Algorithm] 버블(거품) 정렬 - Bubble Sort

진행 순서

1. 서로 인접한 두 원소 대소를 비교하고
2. 정렬하고자 하는 조건에 맞지 않다면 자리를 교환

코드

void bubbleSort() {
	int arr[5] = {5, 4, 3, 2, 1};
	for(int i=0; i<5; ++i){ // 정렬된 원소의 갯수 카운팅
		for(int j=1; j<5-i; ++j){ // 원소를 비교할 index 순회
			if(arr[j-1] > arr[j]) {
				int tmp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = tmp;
			}
		}
	}
}

시간 복잡도

원소가 정렬되있든, 아니든 모두 탐색함

최선	평균	최악

 

공간 복잡도

한개의 배열 안에서 수행

장점

• 구현 단순
• 정렬하고자 하는 배열안에서 정렬 교환이 발생하므로, 다른 메모리 공간을 필요로 하지 않는다.
• stable sort
  • 동일한 정렬 기준(같은 크기의 원소)을 가진 것은 정렬 후 위치가 같다.

단점

• 최선, 평균, 최악이 O(N^2)으로 비효율
• 정렬되어 있지 않은 원소가 많으면 SWAP이 많이 발생