[C언어] 버블 정렬

버블 정렬(Bubble Sort) 알고리즘 이란

 

---

#include <stdio.h>
/*
	버블 정렬 (오름 차순) 1 2 3 ->
	7 4 5 1 3	:: 기본 
	4 5 1 3 7	:: 1회 
	4 1 3 5 7	:: 2회 
	1 3 4 5 7	:: 3회 
	1 3 4 5 7	:: 4회 
	
	특징 1 : 버블 정렬을 1회 시도하면 배열에서 가장 큰 수 하나가 오른쪽으로 무조건 지정
	특징 2 : 버블 정렬을 [n - 1] 회 시도하면 오름 차순으로 정렬이 완료 된다. 
*/


// 기존 값이 비교 값보다 크다면, 기존 값을 빈 값에 넣어두고 
// 기존 값에 비교 값을 넣고 비교 값에 기존 값을 넣는다. 
void BubbleSort(int arr[], int n) {
	int i, j, k;
	int temp;
	
	for(i = 0; i < n - 1; i++) {
		printf("[%d 번] ", i);
		
		for(j = 0; j < n; j++) {
			printf("%d ", arr[j]);
		}
		
		printf("\n");
		
		// 뒤에 있는 인덱스 번호는 어차피 큰 값으로 있는 값이므로 계산을 안해도 된다.
		// 그래서 n - j - 1 형식으로 만들어준다. 
		for(k = 0; k < (n-i-1); k++) {
			if(arr[k] > arr[k + 1]) {
				temp = arr[k];
				arr[k] = arr[k + 1];
				arr[k + 1] = temp;
			}
		}
	}
}

int main(void) {	

	
	int arr[5] = {7, 4, 5, 1, 3};
	
	BubbleSort(arr, sizeof(arr)/sizeof(int));
	
	int i;
	
	printf("\n[버블 정렬] ");
	for(i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}
	
	
	return 0;
}

 

 

---

버블 정렬(Bubble Sort) 알고리즘의 특징

 

장점

• 구현이 매우 간단하다.

단점

• 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
• 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.

일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

 

버블 정렬(Bubble Sort)의 시간복잡도

 

비교 횟수

• 최상, 평균, 최악 모두 일정
• n-1, n-2, … , 2, 1 번 = n(n-1)/2

교환 횟수

• 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
• 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.

T(n) = O(n^2)

단순(구현 간단)하지만 비효율적인 방법

• 삽입 정렬, 선택 정렬, 버블 정렬

복잡하지만 효율적인 방법

• 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

 

- 내용 출처

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html