[알고리즘] 버블 정렬(bubble sort) 란 - travelbeeee

안녕하세요, 여행벌입니다.

오늘은 버블 정렬(bubble sort)에 대해서 포스팅해보겠습니다.

---

버블 정렬이란

'서로 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환 해나가는 정렬 방식'

---

EX)

바로 예시를 통해서 익혀보겠습니다.

[ 2 3 5 1 4 ] 5개의 숫자가 담긴 배열을 버블 정렬을 통해서 정렬해보도록 하겠습니다.

 

STEP 1]

앞에서부터 차례대로 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환해나가겠습니다.

2 와 3은 정렬이 잘 되어있으므로 교환을 하지 않고 3과 5도 마찬가지이므로 넘어갑니다.

5와 1은 크기가 순서대로 되어 있지 않으므로 둘이 교환해주고 5와 4도 마찬가지로 교환해줍니다.

그 결과 가장 큰 값인 5가 제일 뒤로 가게 되고 5는 정렬이 완료됩니다.

STEP 2]

마찬가지로 동일한 작업을 반복합니다.

2와 3은 PASS , 3과 1은 정렬이 되어있지 않으므로 SWAP을 진행해주고 3과 4는 PASS 합니다.

Unsorted에서 가장 큰 값인 4가 제일 뒷부분으로 가면서 정렬이 완료됩니다.

STEP 3]

STEP 4]

최종적으로 4개의 값들이 정렬이 되면서 마지막 값도 자동으로 정렬이 됩니다.

선택 정렬과 반대로 가장 큰 값이 제일 뒤로 정렬되는 것을 확인할 수 있습니다.

---

코드 구현

코드는 다음과 같습니다.

void bubble_sort(int list[], int n) {
	int temp;
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			// 정렬되어있지않다면 SWAP 한다.
			if (list[j] > list[j + 1]) {
				temp = list[j];
				list[j] = list[j + 1];
				list[j + 1] = temp;
			}
		}
	}
}

---

복잡도 분석

N 개의 원소가 있다고 가정하고 버블 정렬의 복잡도를 분석해보겠습니다.

버블 정렬은 처음에 ( N - 1 ) 번의 비교 연산이 발생하고, 선택 정렬과 마찬가지로 정렬이 완성된 부분이 하나씩 늘어가며 비교 연산이 1회씩 감소합니다.

따라서, 총 ( N - 1 ) + ( N - 2 ) +  ⋯ + 1 번 비교 연산이 발생합니다.

등차수열의 합으로 O ( N ^ 2 ) 의 시간 복잡도를 가지는 것을 확인할 수 있습니다.

배열이 이미 정렬이 되어있더라도 항상 똑같은 비교 과정을 거치므로 최선, 평균, 최악의 경우에 대해서 시간 복잡도가 동일합니다.

 

---

안정 정렬

버블 정렬은 '안정 정렬' 입니다. 즉, 동일한 원소 간의 순서가 정렬 후 바뀌지 않습니다.

[ 5-1  2  1  5-2 ] 를 버블 정렬을 통해서 정렬해보겠습니다.

동일한 두 원소 5를 구분하기 위해 5-1 / 5-2 로 표현했습니다.

 

정렬 전 [ 5-1  2  1  5-2 ] →  정렬 후 [ 1  2  5-1  5-2 ] 

 

다음과 같이 버블 정렬은 안정 정렬인 것을 확인할 수 있습니다.

---

이상으로 버블 정렬 포스팅을 마치겠습니다.