[알고리즘] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)은 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행한다.

 

 - 코드 구현이 간단하다.

 - O(n²)의 시간 복잡도를 갖는다.

 

 

기본 동작 과정

배열에 저장된 값을 오름차순 정렬으로 할 때 다음과 같은 동작 과정을 수행한다.

 

 ① 배열의 첫 번째 값(비교할 값)과 두 번째 값(비교되는 값)을 비교한다.

 

 

 ② 비교되는 값이 더 작으면 교환한다.

 

 

 ③ 배열의 시작 인덱스를 하나 증가하여 과정 ① 반복한다.

 

 

 

 

 

 ④ 배열의 마지막 인덱스까지 비교하면 맨 마지막 값은 정렬된 상태이다.

 

1회

 

 ⑤ 모든 값이 정렬될 때까지 과정 ①, ②, ③, ④ 반복한다.

 

2회

 

3회

 

4회

 

최종

 

알고리즘 분석

버블 정렬의 복잡도는 항상 O( n² )의 시간 복잡도를 갖는다.

 

최악의 경우

 - 비교 횟수 : n ( n - 1 ) / 2

 - 이동 횟수 : 비교 횟수 * 3

 

최선의 경우

 - 비교 횟수 : n ( n - 1 ) / 2
 - 이동 횟수 : 0

 

버블 정렬 소스 코드

#include <stdio.h>

#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )

void Print(int arr[], int length) {
	printf("---- * Bubble Sort 결과 * ----\n");
	for (int i = 0; i < length; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n------------------------------\n");
}

// 오름차순 버블 정렬
void BubbleSort(int arr[], int length) {
	int temp;

	for (int i = length - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1])
				SWAP(arr[j], arr[j + 1], temp);
		}
	}
}

void main() {
	int data[5] = { 3, 1, 4, 5, 2 };
	int length = sizeof(data) / sizeof(int);

	BubbleSort(data, length);
	Print(data, length);
}