[알고리즘] 버블 정렬 정리 및 구현

버블 정렬 정리

 

 오늘은 정렬 알고리즘 중 시간이 다소 걸리는 버블 정렬(bubble sort)를 정리하도록 하겠습니다.

 

버블 정렬이란?

 버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다. 즉, 바로 옆에 있는 요소를 검사하여 원하는 순서가 되도록 두 원소를 바꾸어주며 진행하게 됩니다.

 

버블 정렬 구체적인 설명

 

 버블 정렬은 인접한 두 원소를 비교하며 정렬하는 방법입니다. 우선은 첫 번째 자료(0번째 인덱스 값)와 두 번째 자료(1번째 인덱스 값)을 비교, 그리고 두 번째 자료와 세번째 자료를 비교.... 이런 빙식으로 마지막 이전 요소 n-1과 n번째 자죠를 비교, 교환하며 정렬을 진행하게 됩니다. 

 

 처음 0번 인덱스부터 시작하여 비교를 진행하였을 때, 그 1회전이 끝나면 가장 큰 자료(혹은 가장 작은 자료)는 맨 뒷 순서로 가게 됩니다. 그러므로 1번 인덱스부터 시작하는 다음 진행부터는 마지막 요소는 정렬에서 제외하게 됩니다. 즉, 1회전 수행 시마다 마지막 요소 하나씩을 정렬 대상에서 제외시키게 됩니다.

 

버블 정렬 진행 예시

 

버블 정렬 원래 자료

위의 사진은 원래 자료입니다. 우리의 목표는 큰 숫자부터 작은 숫자 순으로(내림차순) 나열을 하는 것입니다.

---

 

1회전

우선 첫0번째 요소 3과  1번째 요소 0을 비교합니다. (순번을 0부터 시작하겠습니다.)

버블 정렬

---

다음, 1번째 요소와 2번째 요소를 비교합니다.여기서 2가 0보다 크므로 두 수를 바꾸어줍니다.

버블 정렬

---

다음으로 2번째 요소와 3번째 요소를 비교합니다. 4가 0보다 크므로 두 수를 바꾸어줍니다.

버블 정렬

---

다음으로 3번째 요소와 4번째 요소를 비교합니다. 1이 0보다 크므로 자리를 바꾸어줍니다.

버블 정렬

 

이렇게 하여 1회전이 끝나게 되었습다. 가장 작은 수인 0이 맨 뒤로 가게 된 것을 볼 수 있습니다. 이제 맨 뒤의 요소를 정렬 대상에서 제외하고 다시 처음부터 시작하게 됩니다.

 

---

 

2회전

 

처음으로 돌아가 0번째 요소와 2번째 요소를 비교합니다.

버블정렬 2회전

---

다음으로 1번째 요소와 2번째 요소를 비교합니다. 4가 2보다 크므로 두 수의 자리를 바꿉니다.

버블 정렬

---

다음 2번째 요소와 3번째 요소를 비교합니다. 결국 비교하는 수 중 제일 작은 1이 맨 뒤로 오게 되었습니다. 1을 비활성화합니다. 그리고 다시 처음으로 돌아갑니다.

 

---

 

3회전

다시 처음으로 돌아가 0번 요소와 1번 요소를 비교합니다. 4가 3보다 크므로 자리를 바꾸어줍니다.

버블정렬 3회전

---

1번 요소와 2번 요소를 비교합니다.

 

회전이 끝났으므로 마지막 요소를 검사에서 제외합니다. 그리고 다시 새로운 회전을 시작합니다.

---

 

4회전

 

0번 요소와 1번 요소를 비교합니다. 이로서 모든 수가 내림차순으로 정렬 되어 있는 것을 확인 할 수 있습니다.

 

버블정렬 최종 모습

 

 

버블정렬 구현 (C언어)

#include <stdio.h>

void swap();

int main(void){
	int nums[] = {3, 0, 2, 4, 1};
	int i, j, temp;
	for(i = 0; i < 5; i++){
		for(j = 0; j < 4-i; j++){
			if(nums[j] < nums[j+1]){
				swap(&nums[j], &nums[j+1]);
			}
		}
	}
	 
	for(i = 0; i < 5; i++){
		printf("%d ", nums[i]);
	}
	return 0;
}

void swap(int* num1, int* num2){
	int temp;
	temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

간단 정리:

for(i = 0; i <5; i++) : 회전 수를 돌리기 위한 for문

for(j = 0; j < 4-i; j++) : 인접한 요소 비교를 위한 for 문, 한 회전을 돌 때마다 마지막 요소가 제외되어야하고, 배열의 인덱스 값이 4까지이므로 j < 4-i

if(nums[j] < nums[j+1]) : 바로 옆의 배열 요소를 비교, 부호를 반대로 하면 오름차순 정렬 가능

swap(): 두 값을 바꾸기 위한 함수, 포인터 이용( 관련 링크 )

 

버블 정렬 장단점

 

버블 정렬의 장점

- 코드 구현이 단순하며 직관적이다.

 

버블 정렬의 단점

 - 비효율적이다. 최악이든 최선이든 O(N²)의 시간 복잡도를 가지기 때문이다.